网站建设需求文章,凤阳做网站,php网站权限设置,网上买卖交易平台有哪些今天的练习基本就是回溯法组合问题#xff0c;这一节只要看labuladong即可。 组合问题#xff1a; 39. 组合总和---------------------形式三#xff0c;元素无重可复选 链接#xff1a;代码随想录 一次对#xff0c;同样在进入下次循环时#xff0c;注意startindex是从j… 今天的练习基本就是回溯法组合问题这一节只要看labuladong即可。 组合问题 39. 组合总和---------------------形式三元素无重可复选 链接代码随想录 一次对同样在进入下次循环时注意startindex是从j开始还是j1开始 画图 代码 class Solution {
public:
// 同一个数字可以无限制重复被选取 。如果至少一个数字的被选数量不同则两种组合是不同的。
vectorvectorintv;
vectorintmv;vectorvectorint combinationSum(vectorint candidates, int target) {backtracing(candidates,target,0);return v;}void backtracing(vectorint candidates,int target,int startIndex){if(target0){return;}else if(target0){v.push_back(mv);}else{for(int jstartIndex;jcandidates.size();j){mv.push_back(candidates[j]);backtracing(candidates,target-candidates[j],j);mv.pop_back();}}}
}; 代码随想录版基本一样 class Solution {
private:vectorvectorint result;vectorint path;void backtracking(vectorint candidates, int target, int sum, int startIndex) {if (sum target) {result.push_back(path);return;}// 如果 sum candidates[i] target 就终止遍历for (int i startIndex; i candidates.size() sum candidates[i] target; i) {sum candidates[i];path.push_back(candidates[i]);backtracking(candidates, target, sum, i);sum - candidates[i];path.pop_back();}}
public:vectorvectorint combinationSum(vectorint candidates, int target) {result.clear();path.clear();sort(candidates.begin(), candidates.end()); // 需要排序backtracking(candidates, target, 0, 0);return result;}
}; 40.组合总和II --------------形式二元素可重不可复选 链接代码随想录 代码第一遍做错 class Solution {
public:vectorvectorintv;vectorintmv;vectorvectorint combinationSum2(vectorint candidates, int target) {backtracing(candidates,target,0);return v;}void backtracing(vectorintcandidates,int target,int startIndex){if(target0){return;}else if(target0){v.push_back(mv);}else{for(int jstartIndex;jcandidates.size();j){mv.push_back(candidates[j]);backtracing(candidates,target-candidates[j],j1);mv.pop_back();}}}
}; 报错 125 215重复 看labuladong这一节讲的非常非常清晰 一开始写的j大于0不对 class Solution {
public:
//当给出的数组中存在重复的元素时要通过给定数组的排序对组合/排列问题 排序进行去重
vectorvectorintv;
vectorintmv;vectorvectorint combinationSum2(vectorint candidates, int target) {sort(candidates.begin(),candidates.end());backtracing(candidates,target,0);return v;}void backtracing(vectorint candidates,int target,int startIndex){if(target0){return;}else if(target0){v.push_back(mv);}else{for(int jstartIndex;jcandidates.size();j){// 要对同一树层使用过的元素进行跳过if(jstartIndex candidates[j]candidates[j-1])//zhijisuandiyige{continue;}mv.push_back(candidates[j]);backtracing(candidates,target-candidates[j],j1);mv.pop_back();}}}
}; 131.分割回文串 链接代码随想录 我的思路是没有直接看了代码随想录。 也就是隔板法比如string.size16,则有15个空位第一块隔板在15个空位上随便选一个然后再放第二块隔板第二块隔板在第一块隔板后再放第三块隔板第三块隔板在第二块隔板后。 树的每一层是检验放一块隔板、两块隔板。。。直到放到第15块隔板的情况。 逻辑比较复杂。因为下一层是上一层隔板的位置总之看代码随想录我自己的逻辑还是稍微模糊。 class Solution {
public:// 想起最长回文串那道题不懂这里为什么要用回溯。//先写一个回文串的函数.//按照例子一可以重复//貌似是数学里的隔板问题。则对于长度为16的string最多可以放15个隔板。最少可以放1个隔板且是在15个空位中任意放1个、两个。。。15个隔板vectorvectorstringv;vectorstringmv;vectorvectorstring partition(string s) {backtracing(s,0);return v; }void backtracing(string s,int startIndex){if(startIndexs.size()){v.push_back(mv);return;}else{for(int jstartIndex;js.size();j){if(is_huiwen(s,startIndex,j)){mv.push_back(s.substr(startIndex,j-startIndex1));backtracing(s,j1);//这里写错了应该是从下一个位置开始找mv.pop_back();}}}}bool is_huiwen(string s,int l,int r){while(lr s[l]s[r]){l;r--;}if(lr){return true;}return false;}
};
