如何通过算法练习-day22掌握长尾词的运用技巧？

本文共计1292个文字，预计阅读时间需要6分钟。

回溯算法+39. 组合总和+题意：给你一个无重复元素的整数数组candidates和一个目标整数target，找出candidates中所有可以使数字和为target的不同组合，并以列表形式返回。

回溯算法

39. 组合总和

题意：给你一个 无重复元素 的整数数组candidates 和一个目标整数target，找出candidates中可以使数字和为目标数target 的 所有不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。对于给定的输入，保证和为target 的不同组合数少于 150 个。

示例：

思路：本题我们需要清楚组合数组可以有什么组成？

1. 必须是已经给出的元素
2. 元素可以重复，这就意味着可以重复递归很多次，例如：1，2等超小数字

根据组合数组的组成规范，我们可以得出回溯的终止条件：当数组大于等于目标值target时，必须返回，且等于目标值时保存并发返回。其次是回溯算法的具体过程：先将元素添加到组合中，然后继续添加相同的元素进去，直到组合大于等于目标值才返回，说明第一个元素组合结束，然后才引入下一个元素进行替换尝试

C++代码：

vector<vector<int>> arr; vector<int> tmp; int ComTmp(vector<int> tmp)//计算数组的总和 { int sum=0; for(auto e:tmp) { sum+=e; } return sum; } void ComTarArr(vector<int>& candidates,int target,int begin) { if(ComTmp(tmp)>=target)//只要数组总和大于等于目标值都返回，因为组合的数组是没有明确要求的 { if(ComTmp(tmp)==target)//但是只有等于目标值的数组才能保存 { arr.push_back(tmp); } return; } for(int i=begin;i<candidates.size();i++) { tmp.push_back(candidates[i]); ComTarArr(candidates,target,i);//这里没有++，是因为组合中可以使用重复的元素 tmp.pop_back(); } } vector<vector<int>> combinationSum(vector<int>& candidates, int target) { ComTarArr(candidates,target,0); return arr; }

40. 组合总和 II

题意：给定一个候选人编号的集合candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合。candidates中的每个数字在每个组合中只能使用一次。

注意：解集不能包含重复的组合。

示例：

思路：本题我们主要是在组合数组时就排除重复组合的情况，利用bool的数组标记同枝和同层被使用的元素，然后跳过这些被使用的元素；当我们存储tmp时，就说明这是一组未被保存的元素集合

C++代码：

vector<vector<int>> arr; vector<int> tmp; void ComTarArr(vector<int>& candidates,int target,int begin,int sum,vector<bool> block)//三个特殊变量，begin为加入元素下标，sum是组合数组总和，block是标记已经被使用的元素 { if(sum==target) { arr.push_back(tmp); return; } for(int i=begin;i<candidates.size()&&sum<=target;i++) { if(i>0&&candidates[i-1]==candidates[i]&&block[i-1]==false)//排除相同元素的情况和重复组合的情况，例如：1 7，7 1 { continue; } sum+=candidates[i]; block[i]=true;//标记元素同枝被使用 tmp.push_back(candidates[i]); ComTarArr(candidates,target,i+1,sum,block); sum-=candidates[i]; block[i]=false; tmp.pop_back(); } } vector<vector<int>> combinationSum2(vector<int>& candidates, int target) { vector<bool> block(candidates.size(),false); sort(candidates.begin(),candidates.end()); ComTarArr(candidates,target,0,0,block); return arr; }

131. 分割回文串

题意：给你一个字符串s，请你将s分割成一些子串，使每个子串都是回文串。返回s所有可能的分割方案。回文串是正着读和反着读都一样的字符串。

示例：

思路：本题大致思想是在组合时就判断出该组合是否都是回文字符串，然后在回溯终止时直接存储即可。

回溯过程中，先一个个元素截断，必然都是回文的组合，然后再通过回溯，将最后两个字符串结合判断是否回文，这样以此循环类推，即可得到整个组合顺序

C++代码：

vector<vector<string>> arr; vector<string> tmp; bool PalindStr(string s,int left,int right)//验证字符串是否回文 { while(left<=right) { if(s[left]!=s[right]) { return false; } left++,right--; } return true; } void DividStr(string s,int begin) { if(begin>=s.size())//开头已经走到字符串的末尾了，说明组合结束，需要保存 { arr.push_back(tmp); return; } for(int i=begin;i<s.size();i++) { if(PalindStr(s,begin,i))//先判断截断的字符串是否回文，回文才会加入 { string ss=s.substr(begin,i-begin+1); tmp.push_back(ss); } else//如果有一个字符串不是回文，那整个组合就不成立，就不会继续向下判断，直接跳过 { continue; } DividStr(s,i+1); tmp.pop_back(); } } vector<vector<string>> partition(string s) { DividStr(s,0); return arr; }