代码随想录算法刷题训练营day28：LeetCode(93)复原IP地址 、LeetCode(78)子集 、LeetCode(90)子集II

LeetCode(93)复原IP地址
题目

代码

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

class Solution {
    public List<String> result=new ArrayList<>();//存放最终结果
    public List<Integer> path=new ArrayList<>();//存放路径结果
    public  List<String> restoreIpAddresses(String s) {
        int startIndex=0;
        //调用回溯函数
        backtracking(s,startIndex);
        return result;
    }
    public  void backtracking(String s,int startIndex){
        //终止节点
        if(path.size()==4){
            List<Integer> tempdate=Arrays.asList(new Integer[path.size()]);
            Collections.copy(tempdate, path);
            StringBuffer date=new StringBuffer();
            for (Integer tempdate2 : tempdate) {
                date.append(String.valueOf(tempdate2));
                date.append(".");
            }
            date.deleteCharAt(date.length()-1);
            String tempDate=date.toString();
            result.add(tempDate);
            return ;
        }
        //单层递归循环逻辑
        for(int i=startIndex;i<s.length();i++){
            String date1=s.substring(startIndex, i+1);//把数据截取出来
            if(date1.length()>1&&date1.charAt(0)=='0'){
                continue;
            }
            if(date1.length()>3){
                continue;
            }
            int date2=Integer.parseInt(date1);
            if(date2<0||date2>255){

                continue;
            }
            path.add(date2);
            if(path.size()==4&&i+1!=s.length()){
                path.remove(path.size()-1);
                continue;//关键
            }
            backtracking(s, i+1);
            //回溯
            path.remove(path.size()-1);
        }
    }
}

LeetCode(78)子集
题目

代码

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.List;

class Solution {
    public List<List<Integer>> result=new ArrayList<>();
    public List<Integer> path=new ArrayList<>();
    public List<List<Integer>> subsets(int[] nums) {
       /* List<Integer> nullPath=new ArrayList<>();
       result.add(nullPath); */
       int startIndex=0;
       backtracking(nums,startIndex);
       return result;
    }
    public void backtracking(int[] nums,int startIndex){
        //终止条件
        List<Integer> tempDate=Arrays.asList(new Integer[path.size()]);
        Collections.copy(tempDate, path);
        result.add(tempDate);
        for(int i=startIndex;i<nums.length;i++){
            path.add(nums[i]);
            backtracking(nums, i+1);
            path.remove(path.size()-1);
        }
    }
}

LeetCode(90)子集II
题目

代码

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {
    public List<List<Integer>> result=new ArrayList<>();
    public List<Integer> path=new ArrayList<>();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        int startIndex=0;
        //排序
        Arrays.sort(nums);
        int[] used=new int[nums.length];//0代表没使用，1代表使用了
        backtracking(nums,used,startIndex);
        return result;
    }
    public void backtracking(int[] nums,int[] used, int startIndex){
        List<Integer>  tempPath=Arrays.asList(new Integer[path.size()]);
        Collections.copy(tempPath, path);
        result.add(tempPath);

        for(int i=startIndex;i<nums.length;i++){
            if(i>0&&nums[i]==nums[i-1]&&used[i-1]==0){//重点思考
                continue;
            }
            path.add(nums[i]);
            used[i]=1;
            backtracking(nums, used, i+1);
            path.remove(path.size()-1);
            used[i]=0;
        }   
    }
}