代码随想录算法训练营第28天（回溯算法04 |● 93.复原IP地址 ● 78.子集 ● 90.子集II
93.复原IP地址
本期本来是很有难度的，不过 大家做完 分割回文串 之后，本题就容易很多了
题目链接： 93.复原IP地址
文章讲解： 93.复原IP地址
视频讲解： 93.复原IP地址
解题思路
回溯三部曲
- 递归参数
List result存放结果
变量startIndex，记录下一层递归分割的起始位置。
变量pointNum，记录添加逗点的数量 - 递归终止条件
pointNum表示逗点数量，pointNum为3说明字符串分成了4段了。然后验证一下第四段是否合法，如果合法就加入到结果集里。 - 单层搜索逻辑
- 需要判断当前截取的子串[startIndex, i] 是否合法。如果合法就在字符串后面加上符号.表示已经分割。如果不合法就结束本层循环。
- 递归调用时，下一层递归的startIndex要从i+2开始（因为需要在字符串中加入了分隔符.），同时记录分割符的数量pointNum 要 +1。
- 回溯的时候，就将刚刚加入的分隔符. 删掉就可以了，pointNum也要-1。
注意点
- 用StringBuilder进行操作性能更好
- 判断子串是否符合在0~255的函数
- 单层搜索逻辑在一个if else里面，与前面有所不同（这一点需复习加深理解）
- 代码随想录上的剪枝优化代码还没看，复习的时候看
// 使用stringBuilder，故优化时间、空间复杂度，因为向字符串插入字符时无需复制整个字符串，
// 从而减少了操作的时间复杂度，也不用开新空间存subString，从而减少了空间复杂度。
class Solution {
List<String> result = new ArrayList<>();
public List<String> restoreIpAddresses(String s) {
if(s.length() > 12) return result; // 算是剪枝
StringBuilder sb = new StringBuilder(s);
backTracking(sb, 0, 0);
return result;
}
public void backTracking(StringBuilder s, int startIndex, int sumPoint){
if(sumPoint == 3){ // 逗点数量为3时，分割结束
// 判断第四段⼦字符串是否合法，如果合法就放进result中
if(isValid(s, startIndex, s.length() - 1)){
result.add(s.toString());
}
return;
}
for(int i = startIndex; i < s.length(); i++){
if(isValid(s, startIndex, i)){
s.insert(i + 1, '.');
sumPoint++;
backTracking(s, i+2, sumPoint);// 插⼊逗点之后下⼀个⼦串的起始位置为i+2
sumPoint--;
s.deleteCharAt(i + 1);
}else{
break;
}
}
}
//[start, end]
private boolean isValid(StringBuilder 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++){
int digit = s.charAt(i) - '0';
num = num * 10 + digit;
if(num > 255)
return false;
}
return true;
}
}
78.子集
子集问题，就是收集树形结构中，每一个节点的结果。 整体代码其实和 回溯模板都是差不多的。
题目链接： 78.子集
文章讲解： 78.子集
视频讲解： 78.子集
解题思路
标准模板题
其实可以不需要加终止条件，因为startIndex >= nums.length，本层for循环本来也结束了。
注意点
要清楚子集问题和组合问题、分割问题的的区别，子集是收集树形结构中树的所有节点的结果。
而组合问题、分割问题是收集树形结构中叶子节点的结果。
求取子集问题，不需要任何剪枝！因为子集就是要遍历整棵树
遇到的难点
分析result.add(new ArrayList<>(path));这行代码应该放在哪
class Solution {
List<List<Integer>> result = new ArrayList<>();
List<Integer> path = new LinkedList<>();
public List<List<Integer>> subsets(int[] nums) {
backTracking(nums, 0);
return result;
}
public void backTracking(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]);
backTracking(nums, i + 1);
path.removeLast();
}
}
90.子集II
大家之前做了
40.组合总和II和78.子集，本题就是这两道题目的结合，建议自己独立做一做，本题涉及的知识，之前都讲过，没有新内容。
题目链接： 90.子集II
文章讲解： 90.子集II
视频讲解： 90.子集II
解题思路
在 78.子集 的基础上，结合40.组合总和II中的去重逻辑，即可写出
注意点
一定要记得先排序
树层去重，树枝不去重
class Solution {
List<List<Integer>> result = new ArrayList<>();
List<Integer> path = new LinkedList<>();
boolean used[];
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
used = new boolean[nums.length];
backTracking(nums, 0);
return result;
}
public void backTracking(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-1] == nums[i] && used[i-1] == false) continue; // 去重
used[i] = true;
path.add(nums[i]);
backTracking(nums, i + 1);
used[i] = false;
path.removeLast();
}
}
}
原文地址：https://blog.csdn.net/weixin_46743838/article/details/135763058
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！