代码随想录算法训练营第二十一天 | 93.复原IP地址

Day 20 总结

自己实现中遇到哪些困难
- 一句话讲明白问题分类
  - 组合问题和分割问题都是收集树的叶子节点，子集问题是找树的所有节点！
- 切割字符串问题回顾
  - 昨天的切割回文子串，和今天的切割ip地址，都是需要将字符串拆分成 n 份。
  - 只不过每一小份的长度不定，切完当前这一小份，再交给下层去切割剩余部分。
今日收获，记录一下自己的学习时间
- 17:30 - 19:00

93.复原IP地址

题目链接/文章讲解：代码随想录

题目链接：https://leetcode.cn/problems/restore-ip-addresses/

题目描述：

有效 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 中的任何数字。你可以按任何顺序返回答案。

实现思路：

将字符串分隔成四个部分，并且每个部分都是有效的数字0-255。

1.字符串分隔：一定是从前向后进行切割，先切割一个数字出来，然后再对剩下的字符串再次进行切割。然后要检查当前切割出来的字符串是不是合格的，如果前面都切不出来合格的字符串，后面的切割也没有意义，直接结束该分支的搜索。找到了一个合适的字符串，就传递到下层一次，再剩余字符串中继续切割。当前层切割的字符串长度慢慢递增。

2.检查切割的结果：到达搜索树的结尾时，要确保整个字符串已经切割完了，并且切割成了四个部分。排除不符合条件的分支，并把切割完的字符串收集到结果集合中。

代码实现：

class Solution {public List<String> results = new ArrayList<>();public List<String> path = new ArrayList<>();public List<String> restoreIpAddresses(String s) {backtrack(s, 0);return results;}// 参数：// 返回值:public void backtrack(String s, int startIndex) {// 终止条件if (path.size() > 4) {return;} if (startIndex == s.length() && path.size() == 4) {StringBuffer ipAddr = new StringBuffer();for (int i=0; i<4; i++) {ipAddr.append(path.get(i));if (i < 3) {ipAddr.append(".");}}results.add(ipAddr.toString());}// 回溯单层搜索过程for (int i=startIndex; i<s.length(); i++){if (!isValid(s, startIndex, i+1)) {continue;}path.add(s.substring(startIndex, i+1));backtrack(s, i+1);path.remove(path.size()-1);}}public boolean isValid(String s, int start, int end) {if (end - start > 3) {return false;}if (s.charAt(start) == '0') {if (end - start > 1) {return false;}}if (end - start > 2) {if (s.charAt(start) == '0') {return false;}if (Integer.parseInt(s.substring(start,end)) > 255) {return false;}}return true;}
}// 实现方案2
class Solution {List<Integer> path = new ArrayList<>();List<String> results = new ArrayList<>();char[] arr;public List<String> restoreIpAddresses(String s) {arr = s.toCharArray();backtrack(0);return results;}public void backtrack(int startIdx) {if (path.size() > 4 || startIdx > arr.length) return;if (startIdx == arr.length && path.size() == 4) {String s = "";for (Integer i : path) s = s+i+".";results.add(s.substring(0,s.length()-1));}for (int i=startIdx; i<arr.length; i++) {int num = getNum(startIdx, i);if (num == -1) return;path.add(num);backtrack(i+1);path.remove(path.size()-1);}}public int getNum(int start, int end) {// 小于四位数if (end - start >= 3) return -1;// 没有前导0if (arr[start] == '0') {if (end > start) return -1;return 0;}// 1-255int num = 0;while (start <= end) {num = num * 10 + (int)(arr[start++]-'0');}if (num > 255) return -1;return num;}
}

78.子集

题目链接/文章讲解：代码随想录

题目链接：https://leetcode.cn/problems/subsets/

题目描述：

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。解集不能包含重复的子集。你可以按 任意顺序 返回解集。

实现思路：

收集搜索树上的所有节点。

回溯模板：

代码实现：

class Solution {// 全局变量免去参数传递List<List<Integer>> results = new ArrayList<>();List<Integer> path = new ArrayList<>();int[] nums;public List<List<Integer>> subsets(int[] nums) {this.nums = nums;results.add(new ArrayList<>(path)); // 空集backtrace(0);return results;}public void backtrace(int startIdx) {// 到达底搜索树底层，向上返回if (startIdx >= nums.length) return;for (int i=startIdx; i<nums.length; i++) {path.add(nums[i]);results.add(new ArrayList<>(path)); // 收集所有情况backtrace(i+1);path.remove(path.size()-1);}}
}

90.子集II

题目链接/文章讲解：代码随想录

题目链接：https://leetcode.cn/problems/subsets-ii/description/

题目描述：

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的

子集（幂集）。解集不能包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

实现思路：

与上题比较，元素可能出现重复，为了获得不重复的子集，需要层级去重，该层使用过的数字就不能再使用了。对数组进行排序，然后依次挑选不重复元素。

代码实现：

class Solution {List<Integer> path = new ArrayList<>();List<List<Integer>> results = new ArrayList<>();public List<List<Integer>> subsetsWithDup(int[] nums) {Arrays.sort(nums);results.add(new ArrayList<>(path));backtrack(nums, 0);return results;}public void backtrack(int[] nums, int startIdx) {if (startIdx >= nums.length) return;boolean[] used = new boolean[nums.length];for (int i=startIdx; i<nums.length; i++) {used[i] = true;if (i>0 && nums[i] == nums[i-1] && used[i-1]) continue;path.add(nums[i]);results.add(new ArrayList<>(path));backtrack(nums, i+1);path.remove(path.size()-1);}}
}