庆元县住房和城乡建设局网站,为什么不能去外包公司,房地产开发公司怎么注册,秦皇岛软件开发培训77.组合
思路一#xff1a;回溯相当于枚举#xff0c;所以我们遍历1-n的每一个数字#xff0c;然后在遍历第i位的同时递归出第i1~n位的组合结果#xff0c;跟树的形式相似。 如上图所示#xff0c;当长度为k时#xff0c;即退出递归可对遍历到第i位以及剩下位数与k进行比…77.组合
思路一回溯相当于枚举所以我们遍历1-n的每一个数字然后在遍历第i位的同时递归出第i1~n位的组合结果跟树的形式相似。 如上图所示当长度为k时即退出递归可对遍历到第i位以及剩下位数与k进行比较进行一个剪枝比如遍历到4时4后面没有数字不能组成个数为2的组合
class Solution {
public:vectorvectorintres;void judge(int n,int index,int k,vectorintmid){if(mid.size()k){res.push_back(mid);return;}for(int iindex;in-(k-mid.size())1;i){mid.push_back(i);judge(n,i1,k,mid);mid.pop_back(); //回溯不回溯的话无法继续往下}}vectorvectorint combine(int n, int k) {//思路遍历1-n为index然后传入进行第k-index-1的组合使用中间vector保存当vector的sizek时加入resvectorintmid;judge(n,1,k,mid);return res;}
};
216.组合总和III
分析和上一题如出一辙只是多加了一个判断总和不过数字固定到1-9
class Solution {
public:vectorvectorintres;vectorintmid;void backtrace(int k,int n,int sum,int startIndex){if(sumn || mid.size()k)return;if(sumn mid.size()k){res.push_back(mid);return;}for(int istartIndex;i9-(k-mid.size())1;i){sumi;mid.push_back(i);backtrace(k,n,sum,i1);mid.pop_back();sum-i;}}vectorvectorint combinationSum3(int k, int n) {//思路和77题如出一辙backtrace(k,n,0,1);return res;}
};
17.电话号码的字母总和
画图分析 思路一首先横向递归对每一个位置的字符串数组进行递归遍历 其次在递归遍历之前对该位置的字符串数组进行遍历添加 在递归遍历数组结束之后需要回溯删除本数组添加的字符以便于回溯到上一数组
class Solution {
public:vectorstringdists{,,abc,def,ghi,jkl,mno,pqrs,tuv,wxyz};vectorstringres;void backtrace(string digits,int start,stringmid){if(startdigits.size()){//递归遍历终点res.push_back(mid);return;}for(int i0;idists[digits[start]-0].size();i){//纵向遍历char midCdists[digits[start]-0][i];mid.push_back(midC);backtrace(digits,start1,mid);//横向递归遍历mid.pop_back();//回溯}}vectorstring letterCombinations(string digits) {if(digits.size()0) return res;//极端情况string mid;backtrace(digits,0,mid);return res;}
};
131.分割回文串
思路先使用for循环横向遍历从每一个点截取并且判断当前截取的字符串 i 是否为回文串 1.当属于回文串时把当前字符串加入数组并且递归往下从下一个字符开始再次使用for循环横向遍历判断是否是回文字符 2.当不属于回文串时直接返回 注意终止条件当在递归过程中开始截取的位置startIndex大于等于原字符串的长度时表示已经递归到了尽头 class Solution {
public:vectorvectorstring res;vectorstringmid;bool judgeP(const string s,int start,int end){int leftstart,rightend;while(leftright){if(s[left]!s[right--])return false;}return true;}void backtrace(string s,int startIndex){if(startIndexs.size()){res.push_back(mid);return;}for(int istartIndex;is.size();i){if(judgeP(s,startIndex,i)){//判断当前区间内的字符是否回文串string strs.substr(startIndex,i-startIndex1);mid.push_back(str);}else//不是回文跳过continue;backtrace(s,i1);//寻找i1为起始位置的子串mid.pop_back();//回溯}}vectorvectorstring partition(string s) {//首先需要一个函数判断出来的字符是否回文串//思路递归从0开始分割判断backtrace(s,0);return res;}
};
