leetcode算法刷题的第二十天

1.leetcode 39.组合总和

题目链接

这道题里面的数组里面的数字是可以重复使用的，那可能就会有人想，出现了0怎么办，有这个想法的很好，但是题目要求数组里面的数字最小值为1，这就可以让人放心了。但是有总和的限制，所以间接的也有个数的限制。

因为没有个数的限制，所以可能递归没有层数的限制，但是只要选取的元素总和超过了target，就返回。

class Solution {
public:vector<vector<int>> result;vector<int> path;void backtracking(vector<int>& candidates,int target,int sum,int startIndex){if(sum>target){return;}if(sum==target){result.push_back(path);return;}for(int i=startIndex;i<candidates.size();i++){sum+=candidates[i];path.push_back(candidates[i]);backtracking(candidates,target,sum,i);// 不用i+1了，表示可以重复读取当前的数sum-=candidates[i];path.pop_back();}}vector<vector<int>> combinationSum(vector<int>& candidates, int target) {backtracking(candidates,target,0,0);return result;}
};

思路总结：这道题有两点不同：组合没有数量要求以及元素可以无限重复选取。

2.leetcode 40.组合总和II

题目链接

这道题和上一道题目的区别：第一，本题的数组中的每个数字在每个组合中只能使用一次，第二，本题数组的元素是有重复的，而上一题是无重复元素的数组。

最后本题和上一道题的要求是一样的，解集不能包含重复的组合。

本题的难点在于区别2中：集合（数组candidates）有重复元素，但还不能有重复的组合。

一些同学可能想了：我把所有组合求出来，再用set或者map去重，这么做很容易超时！

所以要在搜索的过程中就去掉重复组合。

很多同学在去重的问题上想不明白，其实很多题解也没有讲清楚，反正代码是能过的，感觉是那么回事，稀里糊涂的先把题目过了。

这个去重为什么很难理解呢，所谓去重，其实就是使用过的元素不能重复选取。 这么一说好像很简单！

都知道组合问题可以抽象为树形结构，那么“使用过”在这个树形结构上是有两个维度的，一个维度是同一树枝上使用过，一个维度是同一树层上使用过。没有理解这两个层面上的“使用过” 是造成大家没有彻底理解去重的根本原因。

那么问题来了，我们是要同一树层上使用过，还是同一树枝上使用过呢？

回看一下题目，元素在同一个组合内是可以重复的，怎么重复都没事，但两个组合不能相同。

所以我们要去重的是同一树层上的“使用过”，同一树枝上的都是一个组合里的元素，不用去重。

为了理解去重我们来举一个例子，candidates = [1, 1, 2], target = 3，（方便起见candidates已经排序了）

强调一下，树层去重的话，需要对数组排序！

class Solution {
public:vector<vector<int>> result;vector<int> path;void backtracking(vector<int>& candidates,int target,int sum,int startIndex,vector<bool>& used){if(sum==target){result.push_back(path);return;}for(int i=startIndex;i<candidates.size()&&sum+candidates[i]<=target;i++){// used[i - 1] == true，说明同一树枝candidates[i - 1]使用过// used[i - 1] == false，说明同一树层candidates[i - 1]使用过// 要对同一树层使用过的元素进行跳过if(i>0&&candidates[i]==candidates[i-1]&&used[i-1]==false){continue;}sum+=candidates[i];path.push_back(candidates[i]);used[i]=true;backtracking(candidates,target,sum,i+1,used);// 和39.组合总和的区别1，这里是i+1，每个数字在每个组合中只能使用一次used[i]=false;sum-=candidates[i];path.pop_back();}}vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {vector<bool> used(candidates.size(),false);// 首先把给candidates排序，让其相同的元素都挨在一起。sort(candidates.begin(),candidates.end());backtracking(candidates,target,0,0,used);return result;}
};

补充：这里直接使用startIndex来去重也是可以的，就可以不用used数组。

class Solution {
public:vector<vector<int>> result;vector<int> path;void backtracking(vector<int>& candidates,int target,int sum,int startIndex){if(sum==target){result.push_back(path);return;}for(int i=startIndex;i<candidates.size()&&sum+candidates[i]<=target;i++){// 要对同一树层使用过的元素进行跳过if(i>startIndex&&candidates[i]==candidates[i-1]){continue;}sum+=candidates[i];path.push_back(candidates[i]);backtracking(candidates,target,sum,i+1);// 和39.组合总和的区别1，这里是i+1，每个数字在每个组合中只能使用一次sum-=candidates[i];path.pop_back();}}vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {// 首先把给candidates排序，让其相同的元素都挨在一起。sort(candidates.begin(),candidates.end());backtracking(candidates,target,0,0);return result;}
};

思路总结：关键是去重的逻辑，代码很简单，网上一搜一大把，但几乎没有能把这块代码含义讲明白的，基本都是给出代码，然后说这就是去重了，究竟怎么个去重法也是模棱两可。

3.leetcode 131.分割回文串

题目链接

回文串就是向前和向后读都是相同的字符串。

本题涉及到两个关键问题：第一，切割问题，有不同的切割方式，第二，判断回文。

我们来分析一下切割，其实切割问题类似组合问题。

例如对于字符串abcdef：

组合问题：选取一个a之后，在bcdef中再去选取第二个，选取b之后在cdef中再选取第三个。

切割问题：切割一个a之后，在bcdef中再去切割第二段，切割b之后在cdef中再切割第三段。

class Solution {
public:vector<vector<string>> result;vector<string> path;// 放已经回文的子串//判断是否为回文串bool isH(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;}void backtracking(const string& s,int startIndex){// 如果起始位置已经大于s的大小，说明已经找到了一组分割方案了if(startIndex>=s.size()){result.push_back(path);return;}for(int i=startIndex;i<s.size();i++){if(isH(s,startIndex,i)){// 是回文子串// 获取[startIndex,i]在s中的子串string str=s.substr(startIndex,i-startIndex+1);path.push_back(str);}else{// 不是回文，跳过continue;}backtracking(s,i+1);// 寻找i+1为起始位置的子串path.pop_back();// 回溯过程，弹出本次已经添加的子串}}vector<vector<string>> partition(string s) {backtracking(s,0);return result;}
};

思路总结：

这道题目在leetcode上是中等，但可以说是hard的题目了，但是代码其实就是按照模板的样子来的。

那么难究竟难在什么地方呢？

我列出如下几个难点：

• 切割问题可以抽象为组合问题
• 如何模拟那些切割线
• 切割问题中递归如何终止
• 在递归循环中如何截取子串
• 如何判断回文

我们平时在做难题的时候，总结出来难究竟难在哪里也是一种需要锻炼的能力。

一些同学可能遇到题目比较难，但是不知道题目难在哪里，反正就是很难。其实这样还是思维不够清晰，这种总结的能力需要多接触多锻炼。

本题我相信很多同学主要卡在了第一个难点上：就是不知道如何切割，甚至知道要用回溯法，也不知道如何用。也就是没有体会到按照求组合问题的套路就可以解决切割。

如果意识到这一点，算是重大突破了。接下来就可以对着模板照葫芦画瓢。

但接下来如何模拟切割线，如何终止，如何截取子串，其实都不好想，最后判断回文算是最简单的了。

关于模拟切割线，其实就是index是上一层已经确定了的分割线，i是这一层试图寻找的新分割线

除了这些难点，本题还有细节，例如：切割过的地方不能重复切割所以递归函数需要传入i + 1。

所以本题应该是一道hard题目了。