今日内容
- leetcode. 93 复原IP地址
- leetcode. 78 子集
- leetcode. 90 子集Ⅱ
Leetcode. 93 复原IP地址
文章链接：代码随想录 (programmercarl.com)
题目链接：93. 复原 IP 地址 - 力扣（LeetCode）
也是一个分割问题，但是在这个问题中有几点不一样：
- 分割的停止条件并非是分割符到达字符串尾部时，而是分割符的个数为 3 时。
- 每次分割时要判断当前分割子串的内容，如果其转换成数字后大于255则非法。
- 分割出子串后，如果子串长度大于 1，则要判断其首字母是否为 0，是的话则非法。
故该题目与普通的分割问题相比，要多考虑以上三种情形。
根据上述情形和抽象树形图，写出如下代码：
class Solution {List<String> result = new LinkedList<>();public List<String> restoreIpAddresses(String s) {StringBuilder sb = new StringBuilder(s);backtracking(sb, 0, 0);return result;}// count变量用于记录分割符数量public void backtracking(StringBuilder sb, int startIndex, int count){if (count == 3){ // 当分割符为 3 时，判断最后的子串是否合法if (isRange(sb, startIndex, sb.length() - 1)){result.add(sb.toString());}return;}for (int i = startIndex; i < sb.length(); i++){if (isRange(sb, startIndex, i)){sb.insert(i + 1, ".");backtracking(sb, i + 2, count + 1); // 因为加个分割符，所以下一步应该从 i + 2 开始sb.deleteCharAt(i + 1);} else {break; // 不合法的直接跳过}}}// 判断子串是否合法public boolean isRange(StringBuilder sb, int start, int end){if (start > end){return false;}if (sb.charAt(start) == '0' && start != end){ // 长度大于1，且首位为0，不符合要求return false;}int num = 0;for (int i = start; i <= end; i++){num = num * 10 + (sb.charAt(i) - '0');// 数字大于255，返回falseif (num > 255){return false;}}return true;}
}- 时间复杂度：O(3 ^ 4)，IP地址最多包含4个数字，每个数字最多有3种可能的分割方式，则搜索树的最大深度为4，每个节点最多有3个子节点。
- 空间复杂度：O(n)
Leetcode. 78 子集
文章链接：代码随想录 (programmercarl.com)
题目链接：78. 子集 - 力扣（LeetCode）
又是一个新的回溯题目类型：子集问题。
与组合问题和切割问题不同，这两种问题都是在遍历到叶子节点后才收割结果。但是子集问题是在遍历每个节点时就要收割结果。子集问题就是寻找树的所有节点。
还有一个需要注意，子集问题返回的结果是无序的，和组合问题一样，所以在子集问题中，取过的元素也不会被重复取。
子集问题可以被抽象成如下树形结构图：
每个节点都要获取一次信息。根据上述内容，可以写出如下代码：
class Solution {List<Integer> elem = new LinkedList<>();List<List<Integer>> result = new LinkedList<>();public List<List<Integer>> subsets(int[] nums) {backtracking(nums, 0);return result;}public void backtracking(int[] nums, int startIndex){result.add(new LinkedList<>(elem)); // 收割结果的语句放在了最前面if (startIndex == nums.length){return;}for (int i = startIndex; i < nums.length; i++){elem.add(nums[i]);backtracking(nums, i + 1);elem.remove(elem.size() - 1);}}
}- 时间复杂度：O(n * 2 ^ n)
- 空间复杂度：O(n)
Leetcode. 90 子集Ⅱ
文章链接：代码随想录 (programmercarl.com)
题目链接：90. 子集 II - 力扣（LeetCode）
本题就是 Leetcode. 78 子集 + 40. 组合总和 II - 力扣（LeetCode）的结合。关键点在于去重。
所以直接进行一个缝，代码如下：
class Solution {List<Integer> elem = new LinkedList<>();List<List<Integer>> result = new LinkedList<>();public List<List<Integer>> subsetsWithDup(int[] nums) {Arrays.sort(nums);backtracking(nums, 0);return result;}public void backtracking(int[] nums, int startIndex){result.add(new LinkedList<>(elem));if (startIndex == nums.length){return;}for (int i = startIndex; i < nums.length; i++){if (i > startIndex && nums[i] == nums[i - 1]){continue;} // 去重elem.add(nums[i]);backtracking(nums, i + 1);elem.remove(elem.size() - 1);}}
}- 时间复杂度：O(n * 2 ^ n)
- 空间复杂度：O(n)
总结
做回溯问题时要根据题意，对代码进行适度的功能添加。
子集问题与组合、分割问题不同，子集问题需要对每一个节点的结果都进行返回，也可以被视作是遍历树的所有节点。
