白酒公司网站的建设,合肥婚恋网站建设,合肥房产信息网,重庆免费注册推广网站day27 代码随想录 2023.12.25
1. 39组合总和 这道题还是组合问题#xff0c;一样的代码套路#xff0c;不过就是递归参数不同#xff0c;数组元素可以重复#xff0c;所以是i而不是i1#xff1b;其次就是终止条件#xff0c;当temp的sum大于target则终止#xff0c;当等…day27 代码随想录 2023.12.25
1. 39组合总和 这道题还是组合问题一样的代码套路不过就是递归参数不同数组元素可以重复所以是i而不是i1其次就是终止条件当temp的sum大于target则终止当等于时则加入到result中; 越来明白回溯本质就是穷举了就是试探所有可能得组合等有满足要求的添加到结果中即可。
class Solution {
public:vectorvectorint result;vectorint temp;vectorvectorint combinationSum(vectorint candidates, int target) {backtravel(candidates, target, 0);return result;}void backtravel(vectorint candidates, int target, int index){int sum0;for(int i0;itemp.size();i){sum temp[i];}if(sumtarget)return;if(sumtarget){result.push_back(temp);return;}for(int iindex;icandidates.size();i){temp.push_back(candidates[i]);backtravel(candidates,target,i);temp.pop_back();}}
};
2. 40组合总和Ⅱ 乍一看以为一样细看后发现首先不允许重复使用所以递归参数是i1其次也是本题的关键数组中会出现重复数字但是结果不允许出现重复因此在第一层递归中遇到相同的值就要越过这里要注意是递归中该层相同的要跳过如果是深度往下递归值相同则不用跳过在开始对数据进行排序这样相同值就相邻了然后递归判断前后相同不相同就跳过
class Solution {
public:vectorvectorint result;vectorint temp;vectorvectorint combinationSum2(vectorint candidates, int target) {sort(candidates.begin(), candidates.end());backtravel(candidates, target, 0);return result;}void backtravel(vectorint candidates, int target, int index){int sum0;for(int i0;itemp.size();i){sum temp[i];}if(sumtarget)return;if(sumtarget){result.push_back(temp);return;}for(int iindex;icandidates.size();i){if (i index candidates[i] candidates[i - 1]) {continue;}temp.push_back(candidates[i]);backtravel(candidates,target,i1);temp.pop_back();}}
};在跳过相同的判断中iindex就是将同层没有相同的如果是i0则是将所有相同元素都越过了
3. 131分割回文子串
class Solution {
public:bool isPalindrome(const string s, int start, int end) {for (int i start, j end; i j; i, j--) {if (s[i] ! s[j]) {return false;}}return true;}vectorvectorstring result;vectorstring temp;vectorvectorstring partition(string s) {backtravel(s,0);return result;}void backtravel(string s, int index){if (index s.size()) {result.push_back(temp);return;}for (int i index; i s.size(); i) {if (isPalindrome(s, index, i)) {temp.push_back(s.substr(index, i - index 1));backtravel(s, i 1);temp.pop_back();}}}
};
