关于网站建设毕业答辩怎么说,我做的网站怎么是危险网站,什么网站可以有人做详情页,wordpress 页面模板插件39 组合总和
题目链接#xff1a;组合总和
思路
这道题目和之前做的组合题目相比#xff0c;就是它可以包含数组中相同的元素(也就是一个元素可以选择多次)。另外一点就是#xff0c;这道题目要注意回溯函数的终止条件#xff0c;否则会无限回溯。
class Solution {
pu…39 组合总和
题目链接组合总和
思路
这道题目和之前做的组合题目相比就是它可以包含数组中相同的元素(也就是一个元素可以选择多次)。另外一点就是这道题目要注意回溯函数的终止条件否则会无限回溯。
class Solution {
public:vectorvectorint res;vectorint path;void backtracking(vectorint nums, int target, int startIndex){if(target 0){return;}if(target 0){res.push_back(path);return;}for(int istartIndex; inums.size(); i){path.push_back(nums[i]);target target - nums[i];backtracking(nums, target, i);target target nums[i];path.pop_back();}}vectorvectorint combinationSum(vectorint candidates, int target) {backtracking(candidates, target, 0);return res;}
};40 组合总和||
题目链接组合总和||
思路
这道题目和上道题目相比给我们的数组中是有重复元素的那么求出来的组合也有可能是重复的同时题目要求不能有重复组合。所以关键点就在于如何去重。
class Solution {
public:vectorvectorint res;vectorint path;void backtracking(vectorint nums, int target, int startIndex, vectorboolused){if(target 0){return;}if(target 0){res.push_back(path);return;}for(int istartIndex; inums.size(); i){if(i0 nums[i]nums[i-1] used[i-1] false){continue;}path.push_back(nums[i]);target - nums[i];used[i] true;backtracking(nums, target, i1, used);target nums[i];used[i] false;path.pop_back();}}vectorvectorint combinationSum2(vectorint candidates, int target) {vectorbool used(candidates.size(), false);sort(candidates.begin(), candidates.end());backtracking(candidates, target, 0, used);return res;}
};这里还是使用了一个used数组来进行去重但是很关键的一步是先要对原始的数组进行排序排完序才可以使用used来记录状态。
26 删除有序数组中的重复项
题目链接删除有序数组中的重复项
思路
看见上一道要去重的题目我就想到如何对数组进行去重呢先给出一种双指针的方法。
class Solution {
public:int removeDuplicates(vectorint nums) {unordered_setint set;int slow 0;for(int fast0; fastnums.size(); fast){if(set.find(nums[fast]) ! set.end()){continue;}else{set.insert(nums[fast]);nums[slow] nums[fast];}}return slow;}
};这道题目还有一个注意点是数组是有序的那么有序如何利用起来呢有序的数组意味着后面的元素绝对不可能和前面已经确认的元素相等。那么我们就不用set这个数据结构。
class Solution {
public:int removeDuplicates(vectorint nums) {int slow 0;for(int fast1; fastnums.size(); fast){if(nums[fast]!nums[slow]){slow;nums[slow] nums[fast];}}return slow1;}
};131 分割回文串
题目链接分割回文串
思路
这道题目初次看感觉还是挺难的。参考解析发现它把分割问题变为了组合问题如果是回文串则第一次分割出的字符就是回文串第二次、第三次也是直到分割完毕。如果第一次分割出来的就不是那么后面肯定也不是。
class Solution {
public:vectorvectorstring res;vectorstring path;bool isPalindrome(const strings, int start, int end){for(int istart, jend; ij; i,j--){if(s[i] ! s[j]){return false;}}return true;}void backtracking(string s, int startIndex){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();}}vectorvectorstring partition(string s) {backtracking(s, 0);return res;}
};参考链接
https://programmercarl.com/0131.%E5%88%86%E5%89%B2%E5%9B%9E%E6%96%87%E4%B8%B2.html#%E6%80%9D%E8%B7%AF
