代码随想录算法训练营第28天

今日任务

● 93.复原IP地址 ● 78.子集 ● 90.子集II

链接：https://docs.qq.com/doc/DUG1yVHdlWEdNYlhZ (opens in a new tab)

93.复原IP地址

自己想法

class Solution {
    public List<String> ans = new ArrayList<>();
    public List<String> tmp = new ArrayList<>();
    public List<String> restoreIpAddresses(String s) {
        backtrack(s, 0, s.length());
        return ans;
    }
    public void backtrack(String s, int start, int end) {
        // 可以在3段的时候就直接判断start到end是否合法，再加入结果集
        if(tmp.size() == 3) {
            String after = s.substring(start, end);
            if(ipCheck(after)) {
                tmp.add(after);
                ans.add(String.join(".", tmp));
                tmp.remove(tmp.size() - 1);
            }
        }
        // 也可以到4段的时候直接加入结果集，当然这样回溯深度会大一丢丢
        // if(tmp.size() == 4 && start == end) ans.add(String.join(".", tmp));
        // else if(start == end) return;
        else {
            for(int i = start; i < end; i++) {
                String front = s.substring(start, i + 1);
                if(ipCheck(front)) {
                    tmp.add(front);
                    backtrack(s, i + 1, end);
                    tmp.remove(tmp.size() - 1);
                }
            }
        }
    }
    public boolean ipCheck(String str) {
        // 如果str长度大于3或等于0，或者不只包含数字，或者长度大于1且以0开头
        if(str == null || str.length() > 3 || str.length() == 0) return false;
        for (char c : str.toCharArray()) {
            if (!Character.isDigit(c)) {
                return false;
            }
        }
        if(str.length() > 1 && str.startsWith("0")) return false;
        int num = Integer.parseInt(str);  // 将str转换为整数
        return num >= 0 && num <= 255;  // 检查num是否在0到255之间
    }
}

78.子集

自己想法

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> subsets(int[] nums) {
        ans.add(new ArrayList<>(path));  // 空集是任意集合的子集
        backtrack(nums, 0, nums.length);
        return ans;
    }
    public void backtrack(int[] nums, int start, int end) {
        if(start == end) return;
        else {
            for(int i = start; i < end; i++) {
                path.add(nums[i]);
                ans.add(new ArrayList<>(path));
                backtrack(nums, i + 1, end);
                path.removeLast();
            }
        }
    }
}

改进：将上面写法的ans.add(new ArrayList<>(path)) 放到backtrack函数的最开始，这样就不用在backtrack函数的最开始单独处理空集了。

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> subsets(int[] nums) {
        // ans.add(new ArrayList<>(path));  // 空集是任意集合的子集
        backtrack(nums, 0, nums.length);
        return ans;
    }
    public void backtrack(int[] nums, int start, int end) {
        ans.add(new ArrayList<>(path));
        if(start == end) return;
        else {
            for(int i = start; i < end; i++) {
                path.add(nums[i]);
                backtrack(nums, i + 1, end);
                path.removeLast();
            }
        }
    }
}

回顾

如果把子集问题、组合问题、分割问题都抽象为一棵树的话，那么组合问题和分割问题都是收集树的叶子节点，而子集问题是找树的所有节点！

90.子集II

自己想法

排序+去重

本题和78题的区别类似“39. 组合总和”与“40.组合总和II”的差异。解题思路也类似

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        backtrack(nums, 0, nums.length);
        return ans;
    }
    public void backtrack(int[] nums, int start, int end) {
        ans.add(new ArrayList<>(path));
        if(start == end) return;
        else {
            for(int i = start; i < end; i++) {
                path.add(nums[i]);
                backtrack(nums, i + 1, end);
                path.removeLast();
                while((i + 1) < end && nums[i] == nums[i + 1]) i++;
            }
        }
    }
}