代码随想录一刷记录Day23——leetcode39. 组合总和 40. 组合总和II 131. 分割回文串

前言之前就有刷代码随想录但奈何总是三天打鱼两天晒网而且刷的也很囫囵吞枣于是乎决定参加代码随想录训练营准备精刷一遍希望自己能坚持下去结营后自己的算法水平能更上一个level冲ingleetcode39. 组合总和题目链接leetcode39. 组合总和思路本题和昨天做的组合问题大体思路是一致的主要区别在于本题所给集合中的元素是可以重复使用的也就是说在往深层递归时startIndex不用在1了让startIndex继续从当前的i开始继续搜索其余步骤依然是遵循回溯三部曲递归参数和返回值不必多说和之前组合问题类似。其中终止条件有两个一个是当前组合总和target那么久把path加入result另一个是当前组合总和target那么直接return。单层搜索逻辑中需要注意的是如何实现重复选取如下行代码backtracking(candidates,target,sum,i);// 关键点:不用i1了表示可以重复读取当前的数另一个需要注意的是本题的剪枝功能实现无剪枝优化时对于sum已经大于target的情况依然进入了下一层递归只是下一层递归结束判断的时候会判断sum target的话就返回。其实如果已经知道下一层的sum会大于target就没有必要进入下一层递归了。本题剪枝依然是在for循环范围上做文章对总集合排序之后如果下一层的sum**就是本层的 sum candidates[i]**已经大于target就可以结束本轮for循环的遍历。for(intistartIndex;icandidates.size()sumcandidates[i]target;i)代码classSolution{private:vectorvectorintresult;vectorintpath;voidbacktracking(vectorintcandidates,inttarget,intsum,intstartIndex){if(sumtarget){return;}if(sumtarget){result.push_back(path);return;}for(intistartIndex;icandidates.size();i){sumcandidates[i];path.push_back(candidates[i]);backtracking(candidates,target,sum,i);// 不用i1了表示可以重复读取当前的数sum-candidates[i];path.pop_back();}}public:vectorvectorintcombinationSum(vectorintcandidates,inttarget){result.clear();path.clear();backtracking(candidates,target,0,0);returnresult;}};leetcode40. 组合总和II题目链接leetcode40. 组合总和II思路本题和39.组合总和 有如下区别1、本题candidates 中的每个数字在每个组合中只能使用一次。2、本题数组candidates的元素是有重复的而39.组合总和是无重复元素的数组candidates本题难点在于区别2中的去重可以使用used作为一个标记数组进行树层上的去重。如果candidates[i] candidates[i - 1] 并且 used[i - 1] false就说明前一个树枝使用了candidates[i - 1]也就是说同一树层使用过candidates[i - 1]。此时for循环里就应该做continue的操作代码classSolution{private:vectorvectorintresult;vectorintpath;voidbacktracking(vectorintcandidates,inttarget,intsum,intstartIndex,vectorboolused){if(sumtarget){result.push_back(path);return;}for(intistartIndex;icandidates.size()sumcandidates[i]target;i){// used[i - 1] true说明同一树枝candidates[i - 1]使用过// used[i - 1] false说明同一树层candidates[i - 1]使用过// 要对同一树层使用过的元素进行跳过if(i0candidates[i]candidates[i-1]used[i-1]false){continue;}sumcandidates[i];path.push_back(candidates[i]);used[i]true;backtracking(candidates,target,sum,i1,used);// 和39.组合总和的区别1这里是i1每个数字在每个组合中只能使用一次used[i]false;sum-candidates[i];path.pop_back();}}public:vectorvectorintcombinationSum2(vectorintcandidates,inttarget){vectorboolused(candidates.size(),false);path.clear();result.clear();// 首先把给candidates排序让其相同的元素都挨在一起。sort(candidates.begin(),candidates.end());backtracking(candidates,target,0,0,used);returnresult;}};leetcode131. 分割回文串题目链接leetcode131. 分割回文串思路本题开始属于回溯算法中另一大类即分割问题。其实和组合问题类似。例如对于字符串abcdef组合问题选取一个a之后在bcdef中再去选取第二个选取b之后在cdef中再选取第三个…。切割问题切割一个a之后在bcdef中再去切割第二段切割b之后在cdef中再切割第三段…。在处理组合问题的时候递归参数需要传入startIndex表示下一轮递归遍历的起始位置在切割问题中startIndex就是切割线。在递归循环中如何截取子串在for (int i startIndex; i s.size(); i)循环中我们 定义了起始位置startIndex那么 [startIndex, i] 就是要截取的子串。代码classSolution{private:vectorvectorstringresult;vectorstringpath;// 放已经回文的子串voidbacktracking(conststrings,intstartIndex){// 如果起始位置已经大于s的大小说明已经找到了一组分割方案了即切割线位于字符串最后了if(startIndexs.size()){result.push_back(path);return;}for(intistartIndex;is.size();i){if(isPalindrome(s,startIndex,i)){// 是回文子串// 获取[startIndex,i]在s中的子串string strs.substr(startIndex,i-startIndex1);path.push_back(str);}else{// 不是回文跳过continue;}backtracking(s,i1);// 寻找i1为起始位置的子串path.pop_back();// 回溯过程弹出本次已经添加的子串}}boolisPalindrome(conststrings,intstart,intend){for(intistart,jend;ij;i,j--){if(s[i]!s[j]){returnfalse;}}returntrue;}public:vectorvectorstringpartition(string s){result.clear();path.clear();backtracking(s,0);returnresult;}};