网站左侧漂浮代码,东莞 网站建设 定制水,网站引进搜索引擎怎么做,百度推广营销中心Leetcode 39. 组合总和
题目链接 39 组合总和
本题目和前面的组合问题差不多#xff0c;只不过这里能重复选取数字#xff0c;还是要注意组合的定义#xff0c;交换数字顺序还是算一个组合#xff0c;所以这里还是用我们的startIndex来记录取的数字到哪里了#xff0c;下…Leetcode 39. 组合总和
题目链接 39 组合总和
本题目和前面的组合问题差不多只不过这里能重复选取数字还是要注意组合的定义交换数字顺序还是算一个组合所以这里还是用我们的startIndex来记录取的数字到哪里了下面上代码
class Solution {private:vectorint path;vectorvectorint result;void backtracking(vectorint candidates, int target,int sum,int startIndex){if(sumtarget){return ;}if(sumtarget){result.push_back(path);return ;}for(int istartIndex;icandidates.size()sumcandidates[i]target;i){//其实如果已经知道下一层的sum会大于target就没有必要进入下一层递归了。//对总集合排序之后如果下一层的sum就是本层的 sum candidates[i]已经大于target就可以结束本轮for循环的遍历。path.push_back(candidates[i]);sumcandidates[i];backtracking(candidates, target,sum,i);// 不用i1了表示可以重复读取当前的数sum-candidates[i];path.pop_back();}}
public:vectorvectorint combinationSum(vectorint candidates, int target) {sort(candidates.begin(), candidates.end());//从小到大排序
backtracking(candidates, target,0,0);return result;}
};
Leetcode 40. 组合总和 II
题目链接 40 组合总和 II
本题目的要求是每个集合的元素只能出现一次所以说我们需要去重如何去重才是本题目的关键其他的地方和上面的题目一样我们将回溯函数转化为树状图其实可以分为两个去重一个是树枝去重一个是树层去重下面用一个图片来体现如何去重
默认sort排序在树枝上的去重我们已经完成我们再看在树层上取第二个1的时候下面的情况12已经在取第一个1时下面的情况中涉及到了因为第一个1后面既有重复的第二个1也有第二个1后面的元素所以第一种1一定会包含第二种1的情况。去重我们就完成了下面直接上代码
class Solution {private:vectorint path;vectorvectorint result;void backtracking (vectorint candidates,int target,int sum,int startIndex,vectorbool used){if(sumtarget){result.push_back(path);return ;}for(int istartIndex;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;}path.push_back(candidates[i]);used[i] true;sumcandidates[i];backtracking(candidates,target,sum,i1,used);sum-candidates[i];used[i] false;path.pop_back();}}
public:vectorvectorint combinationSum2(vectorint candidates, int target) {vectorbool used(candidates.size(),false);初始化sort(candidates.begin(),candidates.end());backtracking(candidates,target,0,0,used);return result;}
};
Leetcode131. 分割回文串
题目链接 131 分割回文串
上面的题目都是组合类的从这个题目开始就进入分割类题目了其实组合和分割是一个意思同样能用树状结构来解决。 除此之外还有几个需要注意的点第一个就是将子字符串传递给path用到了substr s.substr(pos, len)pos默认值为0len的默认值是s.size() - pos转化字符串第二个就是回文字符串的判断最后就是回溯函数的模板了上代码
class Solution {private:vectorstring path;vectorvectorstring result;void backtracking (const string s,int startIndex){if(startIndexs.size()){result.push_back(path);return ;}for(int istartIndex;is.size();i){if(isPalindrome(s,startIndex,i)){string str s.substr(startIndex,i-startIndex1);//转化子字符串path.push_back(str);}else{continue;}backtracking(s,i1);//递归path.pop_back();//回溯}}bool isPalindrome(const string s,int start,int end){for(int istart,jend;ij;i,j--){if(s[i]!s[j]){return false;}}return true;}
public:vectorvectorstring partition(string s) {backtracking(s,0);return result;}
};
end状态不佳啊
