前言
代码随想录算法训练营day28
一、Leetcode 93.复原IP地址
1.题目
有效 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. 1 <= s.length <= 20 2. s 仅由数字组成
来源：力扣(LeetCode) 链接：https://leetcode.cn/problems/restore-ip-addresses
2.解题思路
方法一：回溯
思路与算法
由于我们需要找出所有可能复原出的 IP 地址，因此可以考虑使用回溯的方法，对所有可能的字符串分隔方式进行搜索，并筛选出满足要求的作为答案。
设题目中给出的字符串为 ss。我们用递归函数 dfs(segId,segStart)dfs(segId,segStart) 表示我们正在从 s[segStart]s[segStart] 的位置开始，搜索 IP 地址中的第 segIdsegId 段，其中 segId∈{0,1,2,3}segId∈{0,1,2,3}。由于 IP 地址的每一段必须是 [0,255][0,255] 中的整数，因此我们从 segStartsegStart 开始，从小到大依次枚举当前这一段 IP 地址的结束位置 segEndsegEnd。如果满足要求，就递归地进行下一段搜索，调用递归函数 dfs(segId+1,segEnd+1)dfs(segId+1,segEnd+1)。
特别地，由于 IP 地址的每一段不能有前导零，因此如果 s[segStart]s[segStart] 等于字符 00，那么 IP 地址的第 segIdsegId 段只能为 00，需要作为特殊情况进行考虑。
在搜索的过程中，如果我们已经得到了全部的 44 段 IP 地址(即 segId=4segId=4)，并且遍历完了整个字符串(即 segStart=∣s∣segStart=∣s∣，其中 ∣s∣∣s∣ 表示字符串 ss 的长度)，那么就复原出了一种满足题目要求的 IP 地址，我们将其加入答案。在其它的时刻，如果提前遍历完了整个字符串，那么我们需要结束搜索，回溯到上一步。
3.代码实现
```java class Solution { static final int SEGCOUNT = 4; List ans = new ArrayList (); int[] segments = new int[SEG COUNT];
1. public List<String> restoreIpAddresses(String s) { 2. segments = new int[SEG_COUNT]; 3. dfs(s, 0, 0); 4. return ans; 5. } 6. 7. public void dfs(String s, int segId, int segStart) { 8. // 如果找到了 4 段 IP 地址并且遍历完了字符串，那么就是一种答案 9. if (segId == SEG_COUNT) { 10. if (segStart == s.length()) { 11. StringBuffer ipAddr = new StringBuffer(); 12. for (int i = 0; i < SEG_COUNT; ++i) { 13. ipAddr.append(segments[i]); 14. if (i != SEG_COUNT - 1) { 15. ipAddr.append('.'); 16. } 17. } 18. ans.add(ipAddr.toString()); 19. } 20. return; 21. } 22. 23. // 如果还没有找到 4 段 IP 地址就已经遍历完了字符串，那么提前回溯 24. if (segStart == s.length()) { 25. return; 26. } 27. 28. // 由于不能有前导零，如果当前数字为 0，那么这一段 IP 地址只能为 0 29. if (s.charAt(segStart) == '0') { 30. segments[segId] = 0; 31. dfs(s, segId + 1, segStart + 1); 32. } 33. 34. // 一般情况，枚举每一种可能性并递归 35. int addr = 0; 36. for (int segEnd = segStart; segEnd < s.length(); ++segEnd) { 37. addr = addr * 10 + (s.charAt(segEnd) - '0'); 38. if (addr > 0 && addr <= 0xFF) { 39. segments[segId] = addr; 40. dfs(s, segId + 1, segEnd + 1); 41. } else { 42. break; 43. } 44. } 45. }
}
```
二、Leetcode 78.子集
1.题目
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1：
输入：nums = [1,2,3] 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：
输入：nums = [0] 输出：[[],[0]]
提示：
1. 1 <= nums.length <= 10 2. -10 <= nums[i] <= 10 3. nums 中的所有元素 互不相同
来源：力扣(LeetCode) 链接：https://leetcode.cn/problems/subsets
2.解题思路
方法一：迭代法实现子集枚举
思路与算法
记原序列中元素的总数为 nn。原序列中的每个数字 aiai 的状态可能有两种，即「在子集中」和「不在子集中」。我们用 11 表示「在子集中」，00 表示不在子集中，那么每一个子集可以对应一个长度为 nn 的 0/10/1 序列，第 ii 位表示 aiai 是否在子集中。例如，n=3n=3 ，a={5,2,9}a={5,2,9} 时： 0/10/1 序列 子集 0/10/1 序列对应的二进制数 000000 {}{} 00 001001 {9}{9} 11 010010 {2}{2} 22 011011 {2,9}{2,9} 33 100100 {5}{5} 44 101101 {5,9}{5,9} 55 110110 {5,2}{5,2} 66 111111 {5,2,9}{5,2,9} 77
可以发现 0/10/1 序列对应的二进制数正好从 00 到 2n−12n−1。我们可以枚举 mask∈[0,2n−1]mask∈[0,2n−1]，maskmask 的二进制表示是一个 0/10/1 序列，我们可以按照这个 0/10/1 序列在原集合当中取数。当我们枚举完所有 2n2n 个 maskmask，我们也就能构造出所有的子集。
3.代码实现
```java vmpty() || num != freq.get(size - 1)[0]) { freq.add(new int[]{num, 1}); } else { ++freq.get(size - 1)[1]; } } dfs(0, target); return ans; }
1. public void dfs(int pos, int rest) { 2. if (rest == 0) { 3. ans.add(new ArrayList<Integer>(sequence)); 4. return; 5. } 6. if (pos == freq.size() || rest < freq.get(pos)[0]) { 7. return; 8. } 9. 10. dfs(pos + 1, rest); 11. 12. int most = Math.min(rest / freq.get(pos)[0], freq.get(pos)[1]); 13. for (int i = 1; i <= most; ++i) { 14. sequence.add(freq.get(pos)[0]); 15. dfs(pos + 1, rest - i * freq.get(pos)[0]); 16. } 17. for (int i = 1; i <= most; ++i) { 18. sequence.remove(sequence.size() - 1); 19. } 20. }
}
```
三、Leetcode 90.子集II
1.题目
给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集(幂集)。
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
示例 1：
输入：nums = [1,2,2] 输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
示例 2：
输入：nums = [0] 输出：[[],[0]]
提示：
1. 1 <= nums.length <= 10 2. -10 <= nums[i] <= 10
来源：力扣(LeetCode) 链接：https://leetcode.cn/problems/subsets-ii 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集(幂集)。
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
示例 1：
输入：nums = [1,2,2] 输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
示例 2：
输入：nums = [0] 输出：[[],[0]]
提示：
1. 1 <= nums.length <= 10 2. -10 <= nums[i] <= 10
来源：力扣(LeetCode) 链接：https://leetcode.cn/problems/subsets-ii
2.解题思路
方法一：迭代法实现子集枚举
思路
考虑数组 [1,2,2][1,2,2]，选择前两个数，或者第一、三个数，都会得到相同的子集。
也就是说，对于当前选择的数 xx，若前面有与其相同的数 yy，且没有选择 yy，此时包含 xx 的子集，必然会出现在包含 yy 的所有子集中。
我们可以通过判断这种情况，来避免生成重复的子集。代码实现时，可以先将数组排序；迭代时，若发现没有选择上一个数，且当前数字与上一个数相同，则可以跳过当前生成的子集。
3.代码实现
```java class Solution { List t = new ArrayList (); List > ans = new ArrayList >();
1. public List<List<Integer>> subsetsWithDup(int[] nums) { 2. Arrays.sort(nums); 3. int n = nums.length; 4. for (int mask = 0; mask < (1 << n); ++mask) { 5. t.clear(); 6. boolean flag = true; 7. for (int i = 0; i < n; ++i) { 8. if ((mask & (1 << i)) != 0) { 9. if (i > 0 && (mask >> (i - 1) & 1) == 0 && nums[i] == nums[i - 1]) { 10. flag = false; 11. break; 12. } 13. t.add(nums[i]); 14. } 15. } 16. if (flag) { 17. ans.add(new ArrayList<Integer>(t)); 18. } 19. } 20. return ans; 21. }
}
```
