代码随想录算法训练营第二十四天

LeetCode.93 复原IP地址

题目链接 复原IP地址

题解

class Solution {
    List<String> resList = new ArrayList<String>();
    List<String> res = new ArrayList<String>();
    public List<String> restoreIpAddresses(String s) {
        if(s.length() == 0) return resList;
        dfs(s,0);
        return resList;
    }
    public void dfs(String s,int index){
        if(res.size() == 4){
            if(index == s.length()){
                String tmp = String.join(".",res);
                resList.add(tmp);
            }
            return;
        }
        for(int i = index;i<s.length();i++){
            String tmp = s.substring(index,i + 1);
            if(check(tmp)){
                res.add(tmp);
                dfs(s,i + 1); 
                res.remove(res.size() - 1);
            }
            if(s.charAt(index) == '0') break;
        }
    }
    public boolean check(String s){
        if(s.length() < 1 || s.length() > 3) return false;
        int num = Integer.parseInt(s);
        return false; 
    }
}

解题思路

这段代码解决的是 "恢复 IP 地址" 的问题，即把一个字符串转换为所有可能的有效 IP 地址格式。下面是具体的解题思路：

问题分析

IP 地址由 4 个整数组成，每个整数的范围是 0-255，整数之间用点号分隔，且每个整数不能有前导零（除非这个数本身就是 0）。例如 "25525511135" 可以恢复为 "255.255.11.135" 或 "255.255.111.35"。

核心思路：回溯法（深度优先搜索）

1. 递归分割：将字符串分成 4 个部分，每部分对应 IP 地址的一段
2. 验证有效性：每分割出一段就检查其是否符合 IP 地址的规范
3. 回溯探索：如果当前分割有效则继续递归，否则回溯尝试其他分割方式

代码解析

1. 成员变量：

   • resList：存储所有有效的 IP 地址结果
   • res：存储当前正在构建的 IP 地址的各个部分

2. 主函数restoreIpAddresses：

   • 边界检查：如果输入字符串为空则直接返回空列表
   • 调用深度优先搜索函数dfs开始递归分割
   • 返回所有有效的 IP 地址

3. 深度优先搜索函数dfs：

   • 终止条件：当已分割出 4 个部分时
     • 如果此时刚好遍历完整个字符串，则将当前构建的 IP 地址加入结果集
     • 否则直接返回（这种分割无效）
   • 递归过程：
     • 从当前索引开始尝试分割 1-3 个字符（因为 IP 段最长 3 位）
     • 检查分割出的子串是否有效
     • 如果有效则加入res，继续递归下一段
     • 递归返回后移除最后添加的部分（回溯）
     • 特殊处理：如果当前字符是 '0'，则只能作为单独一段，不能和后面的字符组合

4. 验证函数check：

   • 检查子串长度是否在 1-3 之间
   • 检查转换值是否在 0-255 之间

这种方法通过回溯遍历所有可能的分割方式，同时进行有效性检查，确保只保留符合 IP 地址规范的结果，时间复杂度为 O (3^4)，因为每个 IP 段最多有 3 种可能的分割方式，总共 4 个段。

LeetCode.78 子集

题目链接 子集

题解

class Solution {
    List<List<Integer>> resList = new ArrayList<List<Integer>>();
    List<Integer> res = new ArrayList<>();
    public List<List<Integer>> subsets(int[] nums) {
        if(nums == null || nums.length == 0) return resList;
        dfs(nums,0);
        resList.stream().distinct().collect(Collectors.toList());
        return resList;
    }
    public void dfs(int[] nums,int index){
        resList.add(new ArrayList<>(res));
        for(int i = index;i<nums.length;i++){
            res.add(nums[i]);
            dfs(nums,i+1);
            res.remove(res.size()-1);
        }
    }
}

解题思路

这段代码解决的是 "子集" 问题，即找出一个数组的所有可能子集（幂集）。下面是具体的解题思路：

问题分析

子集问题要求找出一个数组的所有可能子集，包括空集和数组本身。每个元素只能出现一次，且子集之间的顺序不考虑（即 [1,2] 和 [2,1] 视为同一个子集）。

核心思路：回溯法（深度优先搜索）

1. 递归构建：通过递归逐步构建所有可能的子集
2. 选择与不选择：对于每个元素，都有两种选择（加入当前子集或不加入）
3. 避免重复：通过控制遍历起始索引来避免生成重复子集

代码解析

1. 成员变量：

   • resList：存储所有找到的子集结果
   • res：存储当前正在构建的子集

2. 主函数subsets：

   • 边界检查：如果输入数组为空则直接返回空列表
   • 调用深度优先搜索函数dfs开始构建子集
   • 注：代码中的distinct()调用实际不会生效，因为算法本身已保证不会产生重复子集
   • 返回所有子集的集合

3. 深度优先搜索函数dfs：

   • 先将当前构建的子集加入结果集（初始时为包含空集）
   • 遍历过程：
     • 从当前索引index开始遍历数组（保证元素顺序，避免重复子集）
     • 将元素加入当前子集res
     • 递归调用dfs，索引 + 1（确保每个元素只使用一次）
     • 递归返回后移除最后添加的元素（回溯操作）

这种方法的时间复杂度是 O (n×2ⁿ)，其中 n 是数组长度。因为每个元素有选和不选两种可能，总共有 2ⁿ个子集，而每个子集的构建需要 O (n) 的时间。空间复杂度是 O (n)，主要用于递归栈和存储当前子集。

LeetCode.90 子集II

题解链接 子集II

题解

class Solution {
    List<List<Integer>> resList = new ArrayList<List<Integer>>();
    List<Integer> res = new ArrayList<>();
    boolean[] used;
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        if(nums == null || nums.length == 0) return resList;
        Arrays.sort(nums);
        used = new boolean[nums.length];
        dfs(nums,0);
        return resList;
    }
    public void dfs(int[] nums,int index){
        resList.add(new ArrayList<>(res));
        for(int i = index;i<nums.length;i++){
            if (i > 0 && nums[i] == nums[i - 1] &&!used[i - 1]) {
                continue;
            }
            res.add(nums[i]);
            used[i] = true;
            dfs(nums,i+1);
            used[i] =false;
            res.remove(res.size()-1);
        }
    }
}

解题思路

这段代码解决的是 "子集 II" 问题，即在包含重复元素的数组中找出所有不重复的子集。下面是具体的解题思路：

问题分析

与基础子集问题不同，本题的输入数组可能包含重复元素，但要求输出的子集不能有重复。例如，对于数组 [1,2,2]，其所有不重复子集为：[], [1], [2], [1,2], [2,2], [1,2,2]。

核心思路：回溯法 + 去重处理

1. 排序预处理：先对数组排序，使相同元素相邻，为去重做准备
2. 递归构建子集：通过回溯算法构建所有可能的子集
3. 去重逻辑：对于重复元素，只有当前面的相同元素已被使用时，才允许使用当前元素，避免生成重复子集

代码解析

1. 成员变量：

   • resList：存储所有不重复的子集结果
   • res：存储当前正在构建的子集
   • used：布尔数组，标记元素是否已被使用，用于去重判断

2. 主函数subsetsWithDup：

   • 边界检查：处理空数组情况
   • 排序数组：将相同元素放在一起，为去重打基础
   • 初始化used数组
   • 调用dfs开始递归构建子集
   • 返回结果集

3. 深度优先搜索函数dfs：

   • 先将当前子集加入结果集（初始为空集）
   • 遍历过程：
     • 从当前索引index开始遍历（保证元素顺序，避免重复）
     • 去重关键判断：i > 0 && nums[i] == nums[i - 1] && !used[i - 1]
       • 含义：如果当前元素与前一个元素相同，且前一个元素未被使用，则跳过当前元素
       • 作用：确保相同元素只按顺序被选择，避免重复子集
     • 选择元素：将当前元素加入子集，并标记为已使用
     • 递归调用：索引 + 1，继续构建子集
     • 回溯操作：移除元素，标记为未使用

这种算法的时间复杂度是 O (n×2ⁿ)，其中 n 是数组长度，排序需要 O (n log n) 时间。空间复杂度是 O (n)，用于递归栈、res和used数组。

去重逻辑是本题的关键，通过排序和used数组的配合，高效地避免了重复子集的生成，无需事后去重，提升了算法效率。