代码随想录第二十四天| 93.复原IP地址 78.子集 90.子集II

93. 复原IP地址

题目描述

给定一个只包含数字的字符串 s，复原它并返回所有可能的有效 IP 地址格式。

一个有效的 IP 地址 由四个整数部分组成，每部分的取值范围是 0-255，每个部分不能包含前导零。

解题思路

这道题目要求我们将一个数字字符串分割成四个有效的 IP 地址部分。可以使用回溯算法来解决这个问题。回溯法可以帮助我们遍历所有可能的分割方式，然后验证每个分割是否符合有效 IP 地址的规则。

关键点：

1. 回溯法：从字符串的起始位置开始，递归地尝试分割出每一部分，每一部分必须是一个有效的数字，并且不能超过 255。
2. 有效 IP 地址的条件：
   • 每部分数字的范围是 0 到 255。
   • 每部分不能有前导零，除非部分的值是 “0”。
   • 最终结果必须包含四个部分。
3. 分割条件：每次递归时，检查当前子串是否符合条件。如果符合条件，递归继续处理剩余的部分。

步骤：

1. 分割字符串：从字符串的起始位置开始分割，每次分割出一个子串，检查该子串是否有效。
2. 递归处理：如果当前部分有效，递归处理剩余的部分，直到分割出四个部分。
3. 回溯：每当分割出一个有效部分后，恢复状态，继续尝试其他可能的分割方式。
4. 结束条件：当分割出四个部分且整个字符串处理完毕时，将该分割方式保存到结果列表中。

代码实现

class Solution {List<String> result = new ArrayList<>();public List<String> restoreIpAddresses(String s) {if(s.length()>12)return result;treebuilding(s,0,0);return result;}public void treebuilding(String s,int startIndex,int pointSum) {if(pointSum==3){if(check(s,startIndex,s.length()-1)){result.add(s);}return;}for(int i=startIndex;i<s.length();i++){if(check(s,startIndex,i)){s = s.substring(0,i+1)+"."+s.substring(i+1);pointSum++;treebuilding(s,i+2,pointSum);pointSum--;s = s.substring(0,i+1)+s.substring(i+2);}else {break;}}}public boolean check(String s,int start,int end) {if(start>end){return false;}if(s.charAt(start) == '0' && start!=end){return false;}int num = 0;for(int i = start;i<=end;i++){if(s.charAt(i)>'9' || s.charAt(i) < '0'){return false;}num = num*10+(s.charAt(i)-'0');if(num>255){return false;}}return true;}
}

78. 子集

题目描述

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：

• 解集不能包含重复的子集。

解题思路

这道题目要求我们找到数组 nums 的所有可能子集。由于子集的数量为 2^n，其中 n 是数组的长度，因此可以使用回溯算法生成所有可能的子集。

关键点：

1. 回溯法：通过回溯法可以在每一层递归中选择或不选择当前元素，来生成所有的子集。
2. 子集生成：每次递归时，都会向当前路径中添加一个新的元素，同时递归生成后续的子集。每次递归结束后，都会移除当前元素，以尝试其他可能性。
3. 路径管理：使用一个 path 列表来存储当前子集的元素，并在递归过程中进行更新。

步骤：

1. 从空子集开始，逐渐向路径中添加元素，形成一个新的子集。
2. 对于每个元素，可以选择加入子集或不加入子集。
3. 递归处理每个可能的选择，直到遍历完所有元素。
4. 每次递归时，加入当前路径到结果集 result 中，最终返回所有的子集。

代码实现

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

90. 子集 II

题目描述

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

说明：

• 解集不能包含重复的子集。

解题思路

这道题目与第78题“子集”非常相似，但有一个额外的挑战——数组可能包含重复元素，因此我们需要确保生成的子集不会重复。为了处理这个问题，使用 used 数组来避免重复元素的选择。

关键点：

1. 回溯法：和第78题一样，我们使用回溯法生成所有的子集。区别在于这里我们需要处理重复元素，确保不产生重复的子集。
2. 重复元素的处理：为了避免重复的子集，我们在回溯过程中通过 used 数组来标记已经被使用过的元素。当遇到重复元素时，只有当前一个相同元素已经被选择过时，才能选择当前元素。
3. 排序：我们首先对 nums 数组进行排序，这样相同的元素会被放在一起，方便我们在回溯过程中跳过重复的元素。

used 数组的作用：

used 数组是用来标记当前元素是否已经被使用过，以确保我们在回溯的过程中不会选择重复的元素。特别地，used 数组的作用如下：

• 标记已经使用的元素：在每次递归中，如果我们选择了一个元素，就通过将 used[i] 设置为 true 来标记这个元素已经被使用。然后递归处理后续的元素。
• 跳过重复元素：当我们遇到重复元素时，used 数组能够确保我们跳过那些“重复的”分支。具体来说，在遍历过程中，如果当前元素 nums[i] 和前一个元素 nums[i-1] 相等，并且前一个元素没有被选过（即 used[i-1] == false），则跳过当前元素 nums[i]，防止重复子集的生成。

解决重复子集的核心：

1. 排序：对数组进行排序，使得相同的元素相邻。这样在回溯过程中，当遇到重复元素时，可以判断它是否已经被处理过。
2. 跳过重复元素：通过 used 数组来标记每个元素是否被使用过。如果当前元素和前一个元素相同，并且前一个元素没有被使用过，则跳过当前元素，这样可以避免在同一层递归中重复使用相同的元素。

步骤：

1. 排序：首先对数组进行排序，使得相同的元素相邻，便于跳过重复元素。
2. 回溯法：递归地生成所有子集，每次选择一个元素加入当前子集。
3. 跳过重复元素：在遍历元素时，如果当前元素与前一个元素相同，并且前一个元素没有被选择，则跳过当前元素，避免产生重复子集。

代码实现

class Solution {List<List<Integer>> result = new ArrayList<>();LinkedList<Integer> path = new LinkedList<Integer>();boolean[] used;public List<List<Integer>> subsetsWithDup(int[] nums) {if(nums.length==0){result.add(path);return result;}Arrays.sort(nums);used = new boolean[nums.length];treebuilding(nums,0);return result;}public void treebuilding(int[] nums,int startIndex){result.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]){continue;}path.add(nums[i]);used[i] = true;treebuilding(nums,i+1);used[i] = false;path.removeLast();}}
}