-
代码随想录算法训练营第十二天|今天的回溯味儿有点冲
Leecode 40. 组合总和 II
链接：https://leetcode.cn/problems/combination-sum-ii/description/
刚开始做这道题真的遇到过很多问题：本质上是对递归流程的不熟悉
事实上不熟悉递归流程玩儿技巧都是耍流氓
并且，这道题真正有价值的地方就是我们发现问题，然后去debug的过程。通过这个过程我们能学到很多东西
而不是直接看答案
首先看最基础版本的代码
class Solution { public: vector<vector<int>> res; vector<int> vec; // 题目规定了每个元素就只能用一次，所以我们一定要加上step // 并且每次递归的时候都从当前元素的下一个元素开始搜 void recursion(vector<int>& candidates,int tar,int sum,int step) { if(sum > tar) return; if(sum == tar) { res.push_back(vec); return; } for(int i=step;i<candidates.size();i++) { vec.push_back(candidates[i]); recursion(candidates,tar,sum + candidates[i],i+1); vec.pop_back(); } } vector<vector<int>> combinationSum2(vector<int>& candidates, int target) { sort(candidates.begin(),candidates.end()); recursion(candidates,target,0,0); return res; } }; // candidates = [10,1,2,7,6,1,5] // sort -> = [1,1,2,5,6,7,10] // target = 8 // 预期结果 = [[1,1,6],[1,2,5],[1,7],[2,6]] // 输出 = [[1,1,6],[1,2,5],[1,7],[1,2,5],[1,7],[2,6]]- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
第二个[1,2,5]出现的原因显然就是因为我们将vec中的第一个元素1替换成了第二个1，所以也没有再出现[1,1,6]嘛
那么我们为什么不采用set去重呢？这是最直接的想法
然后看set改进后的代码
class Solution { public: set<vector<int>> res; vector<int> vec; void recursion(vector<int>& candidates,int tar,int sum,int step) { if(sum > tar) return; if(sum == tar) { res.insert(vec); return; } for(int i=step;i<candidates.size();i++) { vec.push_back(candidates[i]); recursion(candidates,tar,sum + candidates[i],i + 1); vec.pop_back(); } } vector<vector<int>> combinationSum2(vector<int>& candidates, int target) { sort(candidates.begin(),candidates.end()); recursion(candidates,target,0,0); vector<vector<int>> out (res.begin(),res.end()); return out; } }; // 有超时的情况 // candidates =[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1] // target = 30- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
熟悉递归流程的应该很容易理解为什么超时：当我们递归到第30层的时候，此时的sum就刚好等于target，然后return到29层，29层的for循环+1，递归到31层，31层又return···直到第29层的for循环耗尽，再return到第28层，28层的for循环+1···
所以我们需要想一个办法让后面无效的1都pass
class Solution { public: vector<vector<int>> res; vector<int> vec; // 我们重新将set换成vector，因为不需要set去重了 void recursion(vector<int>& candidates,int tar,int sum,int step) { if(sum > tar) return; if(sum == tar) { res.push_back(vec); return; } for(int i=step;i<candidates.size();i++) { vec.push_back(candidates[i]); recursion(candidates,tar,sum + candidates[i],i + 1); while((i + 1)< candidates.size() && candidates[i+1] == vec[vec.size()-1]) i++; // 如果pop之前发现下一个要加入的元素和即将pop的元素相同，我们就一直让i++ vec.pop_back(); } } vector<vector<int>> combinationSum2(vector<int>& candidates, int target) { sort(candidates.begin(),candidates.end()); recursion(candidates,target,0,0); return res; } };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
实际上，上面加入的这段代码也能处理初代版本中两个[1,2,5]的情况：
加入第一个1之后我们通过for循环遍历了整个数组，得到了三种符合题意的情况[[1,1,6],[1,2,5],[1,7]]，那么此时以元素1为开头的数组就再没有符合题意的情况了，for循环遍历完毕之后就要把第一个元素1给pop出去
注意到了吗，此时sort后的target = [1,1,2,5,6,7,10]中第二个元素也是1，我们利用上面加入的while语句让i直接变成3从而跳过了第2个1，从而避免了重复···
Leecode131. 分割回文串
链接：https://leetcode.cn/problems/palindrome-partitioning/
还算是简单，若是回文串就切分，若不是就接着continue
除此之外我们还要写一个判断是否是回文的函数
// 总是有这种比较抽象的题目 // 先写一个判断回文的函数吧 class Solution { public: vector<vector<string>> res; vector<string> vec; bool isPalindrome(const string &s,int l,int r) { if(!s.size()) return false; if(s.size() == 1) return true; while(l < r) { if(s[l]!=s[r]) return false; l++; r--; } return true; } void recursion(const string &s,int step) { if(step >= s.size()) { res.push_back(vec); return; } // 我们不是枚举每次子串的长度，而是枚举位置看当前串是不是回文串 for(int i = step;i < s.size();i++) { if(isPalindrome(s,step,i)) { string str = s.substr(step,i - step + 1); // 因为substr函数右侧是开区间 vec.push_back(str); } else continue; // 此时我们让step = i + 1 recursion(s,i + 1); vec.pop_back(); } } vector<vector<string>> partition(string s) { // 然后我们在这个函数中调用递归函数 recursion(s,0); // 我们首先从第0个元素开始 return res; } };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
Leecode 93. 复原 IP 地址
一道蛮艰辛的题目，从耗时8ms一直优化到耗时0ms
先来看初代方案:
class Solution { public: // 不能有前导0那么遇见0就只能输出 // 如果子串没有结束或者是目前的数字不够四个，就不记录 // 结束条件是什么？子串结束了，或者是vector中已经有超过四个元素了，我们直接return vector<string> res; vector<string> vec; void recursion(string &s,int step) { if(step > s.size() || vec.size() > 4) return; // 如果当前索引已经走到子串末尾了 if(step == s.size()) { // 并且次数子串中刚好存储了4个字符串 if(vec.size() == 4) { // 用res记录当前结果 string str; for(int i=0;i<3;i++) {str += vec[i];str += '.';} str += vec[3]; res.push_back(str); } return; } // 接下来我们要去搜索合法的数字 for(int i=step;i<s.size();i++) { // 一共定义了两个string // start_char表示这层递归循环刚开始时的首字符 // is_zero表示此次push进vector中的串的首字符 // 一般而言我们判断is_zero是不是0就OK // 但是有一种特殊情况是start_char是1，但是回溯回来由于下一个元素是0，此时is_zero是0，因此下一次回溯会push进0而不是10 // 所以只有同时满足二者都为0的情况下才push进去0 string is_zero = s.substr(i,i + 1); string start_char; if(step + 1 < s.size()) string start_char = s.substr(step,step+1); if(is_zero == "0" && start_char == "0") { vec.push_back(is_zero); // 我们把0给push进去之后 recursion(s,i + 1); vec.pop_back(); } else { string str = s.substr(step,i - step + 1); if(str[0] == '0' && str!="0") return; int number = atoi(str.c_str()); if(number <= 255) { vec.push_back(str); recursion(s,i + 1); vec.pop_back(); } else return; } } } vector<string> restoreIpAddresses(string s) { recursion(s,0); return res; } };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
第一种方案我在遇到0之后会直接push进去，但是由于回溯这里的处理逻辑就会比较复杂，必须同时满足“当前step处的值是0”和“当前选定子串的第一个字符是0”才会把单独的0给push进去
这里举一个反例，为什么不能只满足“当前选定子串的第一个字符是0”就把单独的0给push进去
"010010" 输出 ["0.10.0.0","0.100.1.0"] 预期结果 ["0.10.0.10","0.100.1.0"]- 1
- 2
- 3
- 4
- 5
显然输出结果中的子串并不完整。奇怪，我们不是判断了只有在当前step等于子串末尾的时候才会push进去元素吗？其实是在回溯的时候出现了问题：元素1push进去后又把0给push进去，此时vec中的元素个数大于4了，所以pop出去0，然后return到元素1所在的第五层递归中，for 中i + 1，此时的元素是6，如果我们仅仅判断了s.substr(i,i + 1)，这是0，所以就会把0给单独push进去，而不是10，错就错在这了
所以我们需要同时满足is_zero和start_char同时为0，才会把单独的0给push到vec中去
然后我们来看第二种写法：
第二种写法就是把判断都集中到一个函数中去，因为边写递归函数边判断实在是有些冗余并且复杂
class Solution { public: vector<string> vec; vector<string> res; // 换一种写法吧，专门设计一个函数用来判断当前值是不是合法 bool is_legitimate(string s) { int l = 0,r = s.size() - 1; // 其实不需要只要遇见 0 就将其push进去，只要判断当前切分的子串合不合法就完事了 // 首先判断当前子串的第一个字符是不是0并且只有0 if(s[l] == '0' && r > l) return false; // 然后判断当前值转化为数字后是不是位于0 - 255之间 // 注意atoi函数遇到非数字字符会直接停止，所以若是遇见非法字符，是无法判断当前切割是不是合法的，幸好s仅由数字构成 int num = atoi(s.c_str()); // 错误数据直接爆int了 if(num > 255 || num < 0) return false; return true; } void recursion(string &s,int step) { // 若是当前扫描范围大于等于s.size()，那直接就是不合法的情况 if(step > s.size()) return; if(step == s.size()) { if(vec.size() != 4) return; string str; for(int i=0;i<3;i++) {str += vec[i];str += '.';} str += vec[3]; res.push_back(str); } for(int i=step;i<s.size();i++) { string str = s.substr(step,i - step + 1); if(is_legitimate(str)) { vec.push_back(str); recursion(s,i + 1); vec.pop_back(); } // 考虑一下，当前不合法，后序还会有合法的可能性吗 } } vector<string> restoreIpAddresses(string s) { recursion(s,0); return res; } };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
有个细节，我们在is_legitimate函数中判断当前字符串是不是合法的时候，直接用atoi将字符串转化为int，但是有可能需要转化的串远远超过int范围，而溢出之后再判断是不是比255大就不合适了，所以我们开始的时候就判断这个串的长度是不是大于等于4，若是，那么一定非法，直接return
但是还是不够快，所以后续我们加上了三个剪枝操作
class Solution { public: vector<string> vec; vector<string> res; bool is_legitimate(string s) { if(s.size() > 3) return false; int l = 0,r = s.size() - 1; if(s[l] == '0' && r > l) return false; long long num = atoi(s.c_str()); if(num > 255) return false; return true; } void recursion(string &s,int step) { if(step > s.size()) return; // 再加上一个判断来剪枝，因为正确结果肯定是包含全部数字的 -- 剪枝1 if(vec.size() == 3) if(!is_legitimate(s.substr(step,s.size()))) return; // 判断后面的子串是不是合法，不合法直接return if(step == s.size()) { if(vec.size() != 4) return; string str; for(int i=0;i<3;i++) {str += vec[i];str += '.';} str += vec[3]; res.push_back(str); } for(int i=step;i<s.size();i++) { string str = s.substr(step,i - step + 1); if(is_legitimate(str)) { vec.push_back(str); recursion(s,i + 1); vec.pop_back(); } else return; // 剪枝2 // 考虑一下，当前不合法，后序还会有合法的可能性吗 } } vector<string> restoreIpAddresses(string s) { if(s.size() < 4 || s.size() > 12) return {}; // 剪枝3 recursion(s,0); return res; } };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
剪枝操作解释：
- 第一个剪枝是最有效的：因为符合题意的结果一定是包含所有字符的四个串，因此我们在push进去三个子串后直接判断后序的字符组成的串它是不是合法的，若不是合法的直接return
- 第二个剪枝是在push的时候发生的，若当前子串不合法，那么一定是有前导0或者是值大于255了，那么接着continue让子串边长还会有合法的可能性吗？显然没有，所以else return。这里一定不要直接写return，因为会有回溯，回溯回来肯定不能再return了吧
- 第三个剪枝就是在restoreIpAddresses函数中输入调用递归函数之前，若是判断当前的给的s一定不能组成一个合法的ip地址，就直接return false
Leecode 78. 子集
链接：https://leetcode.cn/problems/subsets/
第一种方法就是枚举当前子串的长度
class Solution { public: // 我的理解其实是for循环中嵌套递归 // 就是从1一直枚举到字符串的长度，分别去搜索答案 // 稍微简化一点的写法就是先把空集和全集给push进去，然后push其他长度的子集 vector<vector<int>> res; vector<int> vec; void recursion(vector<int>& nums,int k,int step) { // 元素收集满了，记录当前vec然后return if(vec.size() == k) { res.push_back(vec); return; } for(int i = step;i<nums.size();i++) { vec.push_back(nums[i]); recursion(nums,k,i + 1); // 是取搜下一个元素了 vec.pop_back(); } } vector<vector<int>> subsets(vector<int>& nums) { // 首先吧空集和全集都给push进去 res.push_back({}); res.push_back(nums); // 依次枚举子串的长度 for(int i = 1; i< nums.size() ;i++) { vec.clear(); recursion(nums,i,0); // 搜i个元素，从第0位开始搜 } return res; } };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
其实我们在搜索的过程中，就出现了全部的子集···
class Solution { private: vector<vector<int>> result; vector<int> path; void backtracking(vector<int>& nums, int startIndex) { result.push_back(path); // 收集子集，要放在终止添加的上面，否则会漏掉自己 if (startIndex >= nums.size()) { // 终止条件可以不加 return; } for (int i = startIndex; i < nums.size(); i++) { path.push_back(nums[i]); backtracking(nums, i + 1); path.pop_back(); } } public: vector<vector<int>> subsets(vector<int>& nums) { result.clear(); path.clear(); backtracking(nums, 0); return result; } };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
真的是需要好好总结的啊
-
相关阅读:
构建有效和安全的远程工作模式
Jetpack Compose 重写TopAppBar 实现标题多行折叠
Docker中OceanBase挂载过后，删除再启动无限重启的解决办法
分布式服务器架构的优点有哪些？
Android：安卓学习笔记之共享元素的简单理解和使用
【云原生 | Kubernetes 系列】--Ceph Dashboard和Ceph 监控
Python视频剪辑神器Auto-Editor使用说明
maven中常用标签
leetcode-1.两数之和
使用JS代理 实现大对象的功能拆解
- 原文地址：https://blog.csdn.net/qq_51537085/article/details/128068022
