电视台网站模版网站关键词部署

当前位置： 首页 > news >正文

电视台网站模版,网站关键词部署,国外网站排名前十,河南国安建设集团有限公司网站不好意思呀各位#xff0c;最近在忙期末考今天才彻底结束#xff0c;来让我们继续算法之路吧~ 题目引用 组合电话号码的字母组合组合总和组合总和II分割回文串 1.组合 给定两个整数 n 和 k#xff0c;返回范围 [1, n] 中所有可能的 k 个数的组合。 你可以按 任何顺序 返回…不好意思呀各位最近在忙期末考今天才彻底结束来让我们继续算法之路吧~ 题目引用 组合电话号码的字母组合组合总和组合总和II分割回文串 1.组合 给定两个整数 n 和 k返回范围 [1, n] 中所有可能的 k 个数的组合。 你可以按 任何顺序 返回答案。 示例 1 输入n 4, k 2 输出 [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ] 我们来看这道回溯入门题首先呢我要说一下我对回溯的想法在我看来回溯其实就是在不断递归的过程中形成了一颗多叉树那么它是个树我们就可以对其的路径进行记录剪枝判断等等一系列操作从而形成一系列的结果集合。 拿这道题目举例我们创建一个全局的res用于记录结果path用于记录多叉树的每一条路径创建一个递归函数先设定函数的出口当我们记录的path.size()k时就说明已经得到一种结果了将path加入到结果数组中。那么递归函数的主体就是把1到n的数都遍历一遍在每条路径中加入当前数值再递归下一个元素返回后pop掉。这其实就是记录树的路径在前些天讲二叉树时已经讲过了。 那么来看代码 class Solution { public:vectorint path;vectorvectorint res;void backtracking(int n,int k,int startIndex){if(path.size()k){res.push_back(path);return;} for(int istartIndex;in;i){path.push_back(i);backtracking(n,k,i1);path.pop_back();}return;}vectorvectorint combine(int n, int k) {backtracking(n,k,1);return res;} };怎么样应该比前几天题目简单不少吧。 2.电话号码的字母组合 给定一个仅包含数字 2-9 的字符串返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 给出数字到字母的映射如下与电话按键相同。注意 1 不对应任何字母。 示例 1 输入digits “23” 输出[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”] 来看这道题目我们乍一眼一看是不是头都大了不知道怎么才能解决这种问题。不急只要我们慢慢分析总能分析出个一二三四首先是电话号码对应的字母我们肯定需要一个表来进行映射再就是如果我们使用回溯的思想那么就要看一下是不是和上一道题相同不同的话应该怎么修改。 可以确定的是这题和上一道题是不太一样的。第一、递归出口不一样。第二、每一层所能选择的元素数目和和元素本身的大小是不确定的。但是好在都能够通过遍历一遍字符串逐层处理逐层确定。 那么来解决这道题吧。首先我们不能使用startIndex来确定每一层的开始位置而是使用Index来作为源字符串内数字的定位然后通过数字在我们自己写好的表中找到对应的数字代表的字符串然后这样每一层的元素才确定了下来再去回溯就很简单的解决了。 来看代码 class Solution { public:string digitsmap[10]{,,abc,def,ghi,jkl,mno,pqrs,tuv,wxyz};vectorstring res;string path;void backtracking(string digits,int Index){if(Indexdigits.size()){res.push_back(path);return;}int digitdigits[Index]-0;string letterdigitsmap[digit];for(int i0;iletter.size();i){pathletter[i];backtracking(digits,Index1);path.pop_back();}return;}vectorstring letterCombinations(string digits) {if(digits) return res;backtracking(digits,0);return res;} };这样写轻轻松松100%啦 3.组合总和 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target 找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 并以列表形式返回。你可以按 任意顺序 返回这些组合。 candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同则两种组合是不同的。 对于给定的输入保证和为 target 的不同组合数少于 150 个。 示例 1 输入candidates [2,3,6,7], target 7 输出[[2,2,3],[7]] 解释 2 和 3 可以形成一组候选2 2 3 7 。注意 2 可以使用多次。 7 也是一个候选 7 7 。 仅有这两种组合。 做完上面那道题做这道题就是小卡拉米了。需要注意的不过是从数组里面直接取出来和可重复但是只要把握住这两个点其实就不会很难。 来看代码 class Solution { public:vectorvectorint res;vectorint path;void backtracking(vectorint candidates,int targetSum,int sum,int startIndex){if(sumtargetSum) return;if(sumtargetSum){res.push_back(path);return;}for(int istartIndex;icandidates.size()sumtargetSum;i){sumcandidates[i];path.push_back(candidates[i]);backtracking(candidates,targetSum,sum,i);sum-candidates[i];path.pop_back();}return;}vectorvectorint combinationSum(vectorint candidates, int target) {backtracking(candidates,target,0,0);return res;} };是不是简简单单呀 4.组合总和II 给定一个候选人编号的集合 candidates 和一个目标数 target 找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字在每个组合中只能使用 一次 。 注意解集不能包含重复的组合。 示例 1: 输入: candidates [10,1,2,7,6,1,5], target 8, 输出: [ [1,1,6], [1,2,5], [1,7], [2,6] ] 我们可以看一下这道题和上一道题目的区别不可重复且只能使用一次。条件是比较苛刻的所以我们就自己加一点工具来限制住这个多叉树的发展其实就有一点点像剪枝了。这里我们加上一个used数组来判断这个数是否被用过再在递归时将startIndex1就可以了。 这里来看代码 class Solution { private:vectorvectorint result;vectorint path;void backtracking(vectorint candidates, int target, int sum, int startIndex, vectorbool 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这里是i1每个数字在每个组合中只能使用一次used[i] false;sum - candidates[i];path.pop_back();}}public:vectorvectorint combinationSum2(vectorint candidates, int target) {vectorbool used(candidates.size(), false);path.clear();result.clear();// 首先把给candidates排序让其相同的元素都挨在一起。sort(candidates.begin(), candidates.end());backtracking(candidates, target, 0, 0, used);return result;} }; 这里大家是不是对树枝和树层比较困惑呢因为同一树层使用过说明我之前已经在这个位置取过这个数了那么我现在再取肯定时重复的同一树枝取过说明我们这一条路径上有一样的元素但是并不是重复取的所以是可以入到path里面的。这样说会不会好一点。 5.分割回文串 给你一个字符串 s请你将 s 分割成一些子串使每个子串都是 回文串 。返回 s 所有可能的分割方案。 示例 1 输入s “aab” 输出[[“a”,“a”,“b”],[“aa”,“b”]] 这道题目就比较难想到了。我们利用startIndex来分割题目给的字符串分割完以后判断这个字符串是不是回文是就赋值给path不是就直接开始下一个循环。判断是不是回文串的方法有很多我们这里采用我们三周之前学过的二分法来做判断是不是不记得了。那么这道题目就做完了。其实这些题目看到答案后都不会觉得很难但难的是想出答案的过程而这也是区分大家的过程。 来看代码 class Solution { public:vectorvectorstring res;vectorstring path;void backtracking(const string s,int startIndex){if(startIndexs.size()) {res.push_back(path);return;}for(int istartIndex;is.size();i){if(ispl(s,startIndex,i)){string strs.substr(startIndex,i-startIndex1);path.push_back(str);}else{continue;}backtracking(s,i1);path.pop_back();}}bool ispl(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;}vectorvectorstring partition(string s) {backtracking(s, 0);return res;} };总结 其实这些题目看到答案后都不会觉得很难但难的是想出答案的过程而这也是区分大家的过程。