代码随想录算法训练营Day21| 93.复原IP地址、78.子集、90.子集||

LeetCode 93 复原 IP 地址

本题思路：最重要的是想到一个收集结果的条件，也就是终止条件。

1. 当 . 的个数达到三个时候，并且，判断最后剩余的是否符合要求，如果符合，说明整个ip地址可以，就加入到结果集中
2. 每次分割的时候，都要判断一次是否满足合法条件，如果合法的进行下一层递归，不合法，就直接进入一个循环。
3. 单层循环完，要记得回溯！

class Solution {
    List<String> res = new ArrayList();
    public List<String> restoreIpAddresses(String s) {
        backtracking(s,0,0);
        return res;
    }
    

    public void backtracking(String s, int startIndex, int postnum){
        if(postnum == 3){
            if(isValid(s,startIndex,s.length()-1)){
                res.add(s);
                return;
            }
        }
        for(int i = startIndex; i < s.length(); i++){
            if(isValid(s,startIndex,i)){
                s = s.substring(0,i+1) + '.' + s.substring(i+1);
                postnum++;
                backtracking(s,i+2,postnum);
                postnum--;
                s = s.substring(0,i+1) + s.substring(i+2);
            }else{
                break;
            }
        }
    }


    // 检查字符串是否有效
    public boolean isValid(String s, int start,int end){
        if(start > end){
            return false;
        }
        if(s.charAt(start) == '0' && start != end){
            return false;
        }
        int sum = 0;
        for(int i = start; i <= end; i++){
            if(s.charAt(i) > '9' || s.charAt(i) < '0'){
                return false;
            }
            sum = sum * 10 + (s.charAt(i) - '0');
            if(sum > 255){
                return false;
            }
        }
        return true;
    }
}

LeetCode 78 子集

本题思路：和组合问题不同的是， 本题没有个数要求，收集的结果集，所以只要遍历到，就要收集。那么就容易很多。

class Solution {

    List<Integer> path = new ArrayList();
    List<List<Integer>> res = new ArrayList();
    public List<List<Integer>> subsets(int[] nums) {
        backtracking(nums,0);
        return res;
    }

    public void backtracking(int[] nums, int startIndex){
        res.add(new ArrayList(path));
        if(startIndex >= nums.length){
            return;
        }
        for(int i = startIndex; i < nums.length; i++){
            path.add(nums[i]);
            backtracking(nums,i+1);
            path.remove(path.size() - 1);
        }
    }
}

LeetCode 90 子集||

本题思路：本题涉及到一个去重操作
去重操作的话，要在树层去重，树枝上不能去重。具体代码思路如下

class Solution {

    List<Integer> path = new ArrayList();
    List<List<Integer>> res = new ArrayList();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        int[] used = new int[nums.length];
        Arrays.sort(nums);
        backtracking(nums,0,used);
        return res;
    }

    public void backtracking(int[] nums, int startIndex,int[] used){
        res.add(new ArrayList(path));
        if(startIndex >= nums.length){
            return;
        }
        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,i+1,used);
            used[i] = 0;
            path.remove(path.size() - 1);
        }
    }
}