算法训练第二十三天|93. 复原 IP 地址 78. 子集 90. 子集 II

93. 复原 IP 地址--分割

题目

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

• 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

示例 1：

输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]

示例 2：

输入：s = "0000"
输出：["0.0.0.0"]

示例 3：

输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

提示：

• 1 <= s.length <= 20
• s 仅由数字组成

题目解析

• 主函数 restoreIpAddresses：

  • 初始化输入字符串 str。
  • 调用 backtrace 方法，从索引0开始递归生成所有可能的IP地址组合。

• 回溯函数 backtrace：

  • 如果 path（存储当前路径的IP段）中正好有4段，且字符串已完全处理完：
    • 将路径拼接成IP地址，加入结果列表 result。
  • 如果超过4段或字符串处理完但不足4段，则直接返回。
  • 遍历字符串，从当前位置 start 开始切分长度为1到3的子串：
    • 检查子串是否是有效IP段（用 isValid 函数）。
    • 如果有效，加入路径并继续递归。
    • 递归完成后回溯，将最后一个加入的段移除。

• 有效性检查 isValid：

  • 检查一个子串是否为合法IP段：
    • 长度为1时，直接合法。
    • 长度大于1时，不能以0开头，且必须在0~255范围内。

class Solution {
    List<String> result = new ArrayList<>();
    List<String> path = new LinkedList<>();
    String str;

    // 递归回溯方法
    public void backtrace(int start) {
        // 如果路径已经有4个段，并且已经处理完字符串，则记录结果
        if (path.size() == 4 && start == str.length()) {
            StringBuilder end = new StringBuilder();
            for (int i = 0; i < path.size(); i++) {
                end.append(path.get(i));
                if (i != path.size() - 1) {
                    end.append(".");
                }
            }
            result.add(end.toString());
            return;
        }
        
        // 如果路径长度大于4段或者已经到达字符串末尾，停止递归
        if (path.size() > 4 || start == str.length()) {
            return;
        }

        // 尝试从当前位置切分1到3位长度的子字符串
        for (int i = start + 1; i <= Math.min(start + 3, str.length()); i++) {
            String segment = str.substring(start, i);
            // 检查段的有效性
            if (isValid(segment)) {
                path.add(segment);
                backtrace(i); // 递归调用处理下一个段
                path.remove(path.size() - 1); // 回溯，去掉当前段
            }
        }
    }

    // 检查一个字符串是否是有效的IP段
    private boolean isValid(String segment) {
        // 不能以"0"开头的多位数字，且必须在0到255之间
        if (segment.length() > 1 && segment.charAt(0) == '0') {
            return false;
        }
        int num = Integer.parseInt(segment);
        return num >= 0 && num <= 255;
    }

    public List<String> restoreIpAddresses(String s) {
        str = s;
        backtrace(0); // 从字符串的第一个字符开始
        return result;
    }
}

78. 子集

题目

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：

输入：nums = [0]
输出：[[],[0]]

提示：

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10
• nums 中的所有元素 互不相同

题目解析

以示例中nums = [1,2,3]为例把求子集抽象为树型结构，如下：

从图中红线部分，可以看出遍历这个树的时候，把所有节点都记录下来，就是要求的子集集合。

这道题就是一道非常标准的回溯法遍历得出结果集的题目

没什么好说的，直接看代码

class Solution {
    List<List<Integer>> result=new ArrayList<>();
    List<Integer>path =new LinkedList<>();
    public void backtrace(int[]nums,int start){
        result.add(new ArrayList<>(path));
        if(start>=nums.length){
            return;
        }
        for(int i=start;i<nums.length;i++){
            path.add(nums[i]);
            backtrace(nums,i+1);
            path.removeLast();
        }
    }
    public List<List<Integer>> subsets(int[] nums) {
        backtrace(nums,0);
        return result;
    }
}

90. 子集 II

题目

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的 子集（幂集）。

解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

示例 1：

输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

示例 2：

输入：nums = [0]
输出：[[],[0]]

题目解析

大体思路和上一题相同，但是多了一个去重的步骤

具体可以看我之前的文章的第二题所用的方法，用一个标记数组在树层进行去重

算法训练第二十二天|39. 组合总和 40. 组合总和 II 131. 分割回文串-CSDN博客

Java代码如下：

class Solution {
    List<List<Integer>> result=new ArrayList<>();
    List<Integer>path =new LinkedList<>();
    boolean []used;
    public void backtrace(int[]nums,int start){
        result.add(new ArrayList<>(path));
        if(start>=nums.length){
            return;
        }
        for(int i=start;i<nums.length;i++){
            if(i>0&&nums[i]==nums[i-1]&&used[i-1]==false){
                continue;
            }
            used[i]=true;
            path.add(nums[i]);
            backtrace(nums,i+1);
            used[i]=false;
            path.removeLast();
        }
    }
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        used=new boolean[nums.length];
        Arrays.fill(used,false);
        Arrays.sort(nums);
        backtrace(nums,0);
        return result;
    }
}