代码随想录第二十四天| 93.复原IP地址 78.子集 90.子集II
93. 复原IP地址
题目描述
给定一个只包含数字的字符串 s，复原它并返回所有可能的有效 IP 地址格式。
一个有效的 IP 地址 由四个整数部分组成，每部分的取值范围是 0-255，每个部分不能包含前导零。
解题思路
这道题目要求我们将一个数字字符串分割成四个有效的 IP 地址部分。可以使用回溯算法来解决这个问题。回溯法可以帮助我们遍历所有可能的分割方式，然后验证每个分割是否符合有效 IP 地址的规则。
关键点：
- 回溯法：从字符串的起始位置开始，递归地尝试分割出每一部分，每一部分必须是一个有效的数字，并且不能超过 255。
- 有效 IP 地址的条件：
- 每部分数字的范围是 0 到 255。
- 每部分不能有前导零，除非部分的值是 “0”。
- 最终结果必须包含四个部分。
- 分割条件：每次递归时，检查当前子串是否符合条件。如果符合条件，递归继续处理剩余的部分。
步骤：
- 分割字符串：从字符串的起始位置开始分割，每次分割出一个子串，检查该子串是否有效。
- 递归处理：如果当前部分有效，递归处理剩余的部分，直到分割出四个部分。
- 回溯：每当分割出一个有效部分后，恢复状态，继续尝试其他可能的分割方式。
- 结束条件：当分割出四个部分且整个字符串处理完毕时，将该分割方式保存到结果列表中。
代码实现
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 是数组的长度，因此可以使用回溯算法生成所有可能的子集。
关键点：
- 回溯法：通过回溯法可以在每一层递归中选择或不选择当前元素，来生成所有的子集。
- 子集生成：每次递归时，都会向当前路径中添加一个新的元素，同时递归生成后续的子集。每次递归结束后，都会移除当前元素，以尝试其他可能性。
- 路径管理：使用一个
path列表来存储当前子集的元素，并在递归过程中进行更新。
步骤：
- 从空子集开始，逐渐向路径中添加元素，形成一个新的子集。
- 对于每个元素，可以选择加入子集或不加入子集。
- 递归处理每个可能的选择，直到遍历完所有元素。
- 每次递归时，加入当前路径到结果集
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 数组来避免重复元素的选择。
关键点：
- 回溯法：和第78题一样，我们使用回溯法生成所有的子集。区别在于这里我们需要处理重复元素，确保不产生重复的子集。
- 重复元素的处理：为了避免重复的子集，我们在回溯过程中通过
used数组来标记已经被使用过的元素。当遇到重复元素时，只有当前一个相同元素已经被选择过时，才能选择当前元素。 - 排序：我们首先对
nums数组进行排序，这样相同的元素会被放在一起，方便我们在回溯过程中跳过重复的元素。
used 数组的作用：
used 数组是用来标记当前元素是否已经被使用过，以确保我们在回溯的过程中不会选择重复的元素。特别地，used 数组的作用如下：
- 标记已经使用的元素：在每次递归中，如果我们选择了一个元素，就通过将
used[i]设置为true来标记这个元素已经被使用。然后递归处理后续的元素。 - 跳过重复元素：当我们遇到重复元素时，
used数组能够确保我们跳过那些“重复的”分支。具体来说，在遍历过程中，如果当前元素nums[i]和前一个元素nums[i-1]相等，并且前一个元素没有被选过（即used[i-1] == false），则跳过当前元素nums[i]，防止重复子集的生成。
解决重复子集的核心：
- 排序：对数组进行排序，使得相同的元素相邻。这样在回溯过程中，当遇到重复元素时，可以判断它是否已经被处理过。
- 跳过重复元素：通过
used数组来标记每个元素是否被使用过。如果当前元素和前一个元素相同，并且前一个元素没有被使用过，则跳过当前元素，这样可以避免在同一层递归中重复使用相同的元素。
步骤：
- 排序：首先对数组进行排序，使得相同的元素相邻，便于跳过重复元素。
- 回溯法：递归地生成所有子集，每次选择一个元素加入当前子集。
- 跳过重复元素：在遍历元素时，如果当前元素与前一个元素相同，并且前一个元素没有被选择，则跳过当前元素，避免产生重复子集。
代码实现
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();}}
}