【算法刷题day28】Leetcode：93. 复原 IP 地址、78. 子集、90. 子集 II

草稿图网站
java的Deque

Leetcode 93. 复原 IP 地址

题目：93. 复原 IP 地址
解析：代码随想录解析

解题思路

“.”参数初始化为0，小于3的时候，每次回溯都在结尾加上一个“.”。
回溯终止条件：“.”参数为4，开始索引等于字符串的长度。

代码

class Solution {
    List<String> res = new ArrayList<>();
    StringBuilder sb = new StringBuilder();
    private boolean isValidSegment(String segment) {
        if (segment.length() > 1 && segment.charAt(0) == '0') // 以0开头的数字段无效
            return false;
        try {
            int num = Integer.valueOf(segment);
            return num >= 0 && num <= 255;
        } catch (NumberFormatException e) {
            return false;
        }
    }
    private void backtracking(String s, int startIndex, int parCount) {
        if (startIndex == s.length() && parCount == 4) {
            res.add(sb.toString());
            return;
        }
        if (startIndex == s.length() || parCount == 4)
            return;
        for (int i = startIndex; i < s.length() && i < startIndex + 3; i++) {
            if (isValidSegment(s.substring(startIndex, i+1))) {
                int len = sb.length();
                sb.append(s.substring(startIndex, i + 1));
                if (parCount < 3)
                    sb.append('.');//最多加三次.
                backtracking(s, i + 1, parCount + 1);
                sb.setLength(len);//直接设置为原来的长度
            }
            
        }
    }
    public List<String> restoreIpAddresses(String s) {
        backtracking(s, 0, 0);
        return res;
    }
}

总结

暂无

Leetcode 78. 子集

题目：78. 子集
解析：代码随想录解析

解题思路

退出条件不需要写

代码

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> paths = new ArrayList<>();
    private void backtracking(int[] nums, int startIndex) {
        res.add(new ArrayList<>(paths));
        for (int i = startIndex; i < nums.length; i++) {
            paths.add(nums[i]);
            backtracking(nums, i + 1);
            paths.remove(paths.size()-1);
        }
    }
    public List<List<Integer>> subsets(int[] nums) {
        backtracking(nums, 0);
        return res;
    }
}

总结

秒了

Leetcode 90. 子集 II

题目：90. 子集 II
解析：代码随想录解析

解题思路

跟上一题的区别是多一个排序和去重

代码

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> paths = new ArrayList<>();
    private void backtracking(int[] nums, int startIndex) {
        res.add(new ArrayList<>(paths));
        for (int i = startIndex; i < nums.length; i++) {
            if (i > startIndex && nums[i] == nums[i-1])
                continue;
            paths.add(nums[i]);
            backtracking(nums, i + 1);
            paths.remove(paths.size()-1);
        }
    }
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        backtracking(nums, 0);
        return res;
    }
}

总结

秒