wap网站要花多少钱,网络会议网站,wordpress主题原理,网站开发验收过程#x1f4dd;个人主页#xff1a;Sherry的成长之路 #x1f3e0;学习社区#xff1a;Sherry的成长之路#xff08;个人社区#xff09; #x1f4d6;专栏链接#xff1a;练题 #x1f3af;长路漫漫浩浩#xff0c;万事皆有期待 文章目录 组合总和 III剪枝 电话号码… 个人主页Sherry的成长之路 学习社区Sherry的成长之路个人社区 专栏链接练题 长路漫漫浩浩万事皆有期待 文章目录 组合总和 III剪枝 电话号码的字母组合总结 组合总和 III
216. 组合总和 III - 力扣LeetCode
组合总和3和上一期的组合思路上差不太多用数字1-9相当于上一道组合题的1-n的范围求解答案而这道题多了一个要想加等于一个固定的数值。
class Solution {
public:vectorvectorint result;vectorint path;void backtracking(int targetSum,int k,int sum,int startIndex){if(path.size()k){if(sumtargetSum){result.push_back(path);}}for(int istartIndex;i9;i){sumi;path.push_back(i);backtracking(targetSum,k,sum,i1);sum-i;path.pop_back();}}vectorvectorint combinationSum3(int k, int n) {result.clear();path.clear();backtracking(n,k,0,1);return result;}
};我们直接向数组里加入数据因为我们暂时不能确定怎样的组合才能凑够n所以我们当数组里元素等于k个数据时直接判断一下如果此时总和等于我们想要的答案那么直接加入答案数组否组向上一层直接返回。而下面的单层递归逻辑是我们仍然用一个start作为开始的下标来记录避免取到重复下标将1-9每一个数都加入进来试错直到找出正确答案。
剪枝
这道题也同样存在可以剪枝的部分这道题可以分成两部分的剪枝也很巧妙。
第一部分的剪枝原因在于这道题是组合求和它给出了一个相加之和为n的组合这个时候我们可以判定当我们此时递归的时候sum当前组合内的值如果大于了给定的目标值n那么很明显我们一定要return了因为是在1-9中取数都是正数怎么加也不可能找的到了。所以第一部分剪枝一定是写在判断部分的代码里这和上一期的组合是有所区别的。
相似的剪枝是第二部分的剪枝 仍然是采用之前的做法剪枝path.size是当前数组中所存的数据有几个k-path.size是还需要几个数字9-k-path.size1是我们最多可以从哪个数字向下进行递归这里的数是从1-9的不是从数组中取数最开始不是0而是1所以要加1。
class Solution {
public:
vectorvectorintresult;
vectorintpath;
void backtraking(int k,int n,int start,int sum){if(sumn) return;if(path.size()k)if(sumn){result.push_back(path);return;}for(int istart;i9-(k-path.size())1;i){path.push_back(i);backtraking(k,n,i1,sumi);path.pop_back();}
}vectorvectorint combinationSum3(int k, int n) {backtraking(k,n,1,0);return result;}
};个人认为的缺陷
第一部分的剪枝是为了避免当sumn时候继续递归第二部分剪枝是告诉最多从哪里开始递归第二部分的剪枝是完全根据传进答案的个数做的剪枝与最终结果n无关。
那么当n100时候k2时候我们还是无法快速的判断当前是无法找的出正确的答案的看到这里可能会去想如果是这种情况还是能很快的判断啊通过第二次剪枝很快就根据k跳出递归了那如果n很大k也很大但是k大也不足以凑出n呢那还是会进行很多次递归-回溯的过程吧做了很多次的搜索但是却一个结果都无法返回但是好像暂时也没有其他什么方法能够比它更好用了。
电话号码的字母组合
17. 电话号码的字母组合 - 力扣LeetCode
这道题也是组合题不过略有一些难度。首先我们要根据它给出的电话按键用map或者数组将其数值所对应的字母都保存起来。然后再构思回溯函数同样的也是创建一个结果数组创立一个中间存数据的数组。这里我们并不需要像start一样作用的变量来指示我们下一次要走向哪一个下标因为这里我们是同时操作多个数组往里面加入数据我们需要的是一个变量告诉我们该遍历哪一个电话按键了它指向的是传进来的电话号码序列的下标。
由于这样的缘故所以我们结束条件可以确定是该变量等于函数传进来的电话号码字符串的字符个数这里有一些疑问为什么我们这个这个变量是表示下标你还要它等于字符序列总个数呢而不是总序列个数减一原因是我们在遍历到最后一个字符时我们仍然需要将最后一个数字对应的字母排列进来而不是直接跳出循环所以我们要等待它这个下标指向最后一个字符的下一个时候才能来做判断。当它与字符序列的个数相等时我们收获结果并想上一层返回以寻求其他结果。
class Solution {
public:string lettermap[10]{,,abc,def,ghi,jkl,mno,pqrs,tuv,wxyz};vectorstring result;string s;void backtracking(const string digits,int index){if(indexdigits.size()){result.push_back(s);return;}int digitdigits[index]-0;string letterslettermap[digit];for(int i0;iletters.size();i){s.push_back(letters[i]);backtracking(digits,index1);s.pop_back();}}vectorstring letterCombinations(string digits) {s.clear();result.clear();if(digits.size()0){return result;}backtracking(digits,0);return result;}
};这里有一些需要我们注意的我们要在循环内创立一个整形来存储该字符序列的某个位置它所代表的数字是什么然后才是用另一个字符串变量来记录该数字所对应的字母序列我们仅需要一个变量来指示下标的原因在上面已经说过了而当它返回到上一层之后我们如何找到上一次对应的电话号码的字母的下一位呢这是递归返回后i所要做的事情我们完全不需要担心其他的单层逻辑和那些组合题大体一样不做赘述。
总结
今天我们完成了组合总和 III\电话号码的字母组合两道题相关的思想需要多复习回顾。接下来我们继续进行算法练习。希望我的文章和讲解能对大家的学习提供一些帮助。 当然本文仍有许多不足之处欢迎各位小伙伴们随时私信交流、批评指正我们下期见~
