【递归、搜索与回溯】综合练习二

devtools/2024/9/24 10:16:22/

综合练习二

  • 1.组合
  • 2.目标和
  • 3.组合总和
  • 4.字母大小写全排列

在这里插入图片描述

点赞👍👍收藏🌟🌟关注💖💖
你的支持是对我最大的鼓励,我们一起努力吧!😃😃

1.组合

题目链接:77. 组合

题目分析:

在这里插入图片描述
注意这道题结果是不能重复的。如1,2 和 2,1 虽然位置不同但是是同样的组合。
在这里插入图片描述

算法原理:
这样的题我们还是画出决策树,然后根据这棵树把所有细节分析清楚

在这里插入图片描述
每个位置都有4种选择,首先前面被选种的数字后面就不能再选了,如1,2 和2,1只是位置不同数都是一样的,因此还是重复。其次上每一层都是从上一层被选数字的后面一个开始选的。全局变量,一个ret记录最终结果,一个path记录每条路径的结果。递归函数,给一个pos,每一层都从pos位置开始往后选,dfs(pos)回溯 当递归结束往上返回要恢复现场pop掉path最后一个位置元素,剪枝 用pos控制开始的位置就是剪枝,递归出口 当path.size() == k 就可以把path放到ret里,然后结束本次递归。

在这里插入图片描述

class Solution {vector<vector<int>> ret;vector<int> path;int n_,k_;
public:vector<vector<int>> combine(int n, int k) {n_=n;k_=k;dfs(1);return ret;}void dfs(int pos){if(path.size() == k_){ret.push_back(path);return;}for(int i=pos;i<=n_;++i){path.push_back(i);dfs(i+1);path.pop_back();//恢复现场}}
};

2.目标和

题目链接:494. 目标和

题目分析:

在这里插入图片描述

给一个数组,对数组每个数字前面添加 + 或者 - ,串联所有数字构成一个表达式,找出表达式和为目标值有多少种情况。

算法原理:
如果前面做过选子集的问题,这道题思想是一模一样的,找子集其中有一张方法是 这个数字 选or不选,这道题就是 这个数字前面 +or-。我们就根据这个画出决策树。
这里的步骤都不说了,和子集哪里的一模一样。最后到叶子节点这条路径的和加起来等于target,就是一种情况。

在这里插入图片描述
这里写代码有两种形式。

  1. path 是全局变量的时候的代码
  2. path 作为参数的代码

可以参考求二叉树所有路径那道题,这道题也是path作为全局变量和作为参数两种不同形式的代码。

path作为全局变量, 需要考虑回溯恢复现场。
path作为参数,不用考虑,因为在递归在向上返回的时候就已经帮助我们回溯恢复现场了。 path作为参数也是有回溯的不过是编译器就可以帮我回溯了。

如果path是一个单独的类型的话,如int类型,你会发现把它放在dfs参数里面写的话,代码比较简洁。如果path是一个数组类型的话,推荐使用全局变量

path作为全局变量的代码

class Solution {int ret,path,_target;
public:int findTargetSumWays(vector<int>& nums, int target) {_target=target;dfs(nums,0);return ret;}void dfs(vector<int>& nums,int pos){if(pos == nums.size()){if(path == _target) ++ret;return;}// 加法path+=nums[pos];dfs(nums,pos+1);path-=nums[pos];// 减法path-=nums[pos];dfs(nums,pos+1);path+=nums[pos];}
};

path作为参数的代码

class Solution {int ret,_target;
public:int findTargetSumWays(vector<int>& nums, int target) {_target=target;dfs(nums,0,0);return ret;}void dfs(vector<int>& nums,int pos,long path){if(pos == nums.size()){if(path == _target) ++ret;return;}// +dfs(nums,pos+1,path+nums[pos]);// -dfs(nums,pos+1,path-nums[pos]);}
};

3.组合总和

题目链接:39. 组合总和

题目分析:
在这里插入图片描述

注意这个数组中的数字,可以无限制重复被选择。但是结果不能有重复的就如下面2,2,3 和 2,3,2是属于同一种组合,只是位置不同罢了。

在这里插入图片描述
算法原理:
暴力枚举所有情况,根据不同的决策树,我们可以写出不同的代码。就比如

  1. 根据每个位置选什么的策略 画决策树
  2. 根据每个数选or不选 画决策树
  3. 考虑每个数用多少个 画决策树

解法一: 根据每个位置选什么的策略 画决策树

每个位置都有三种选择,因为一个数可以被无限制重复选择,所以递归到下一层还可以选。注意3,2 和 2,3 是一样的组合,前面选了后面就不要在选了。并且5,2 和5,3 和2,5 和3,5一样前面选了后面就不要选了。这是一种剪枝情况,还有当一路径的和sum都大于target了就可以结束递归了。这也是一种剪枝情况。

前面我们特别说明一下全局变量的和作为参数的在递归的区别。这里sum求每一条路径的和我们把它作为参数在递归函数中传递,这样每次回溯就不管sum了,而ret和path还是作为全局变量递归函数 我们发现每次都是从本身位置开始往下选,因此 dfs(nums,pos,sum),回溯 sum不用管,path等到递归返回后pop掉最后一个元素,剪枝已经在递归函数中作为pos传递了 ,递归出口 当sum == target 将path放到ret里然后返回,还有一种情况当sum>target不需要往下递归了和pos == nums.size()也不需要往下递归直接返回;
在这里插入图片描述

class Solution {vector<vector<int>> ret;vector<int> path;int aim;
public:vector<vector<int>> combinationSum(vector<int>& candidates, int target) {aim=target;dfs(candidates,0,0);return ret;}void dfs(vector<int>& candidates,int pos,int sum){if(sum >= aim){if(sum > aim) return;if(sum == aim) ret.push_back(path);return;}for(int i=pos;i<candidates.size();++i){path.push_back(candidates[i]);dfs(candidates,i,sum+candidates[i]);path.pop_back();//恢复现场}}
};

解法二: 考虑每个数用多少个 画决策树

每个数可以被选择0-n次,当被选择n次的和都大于target就不能选选了,也就是说小于或者等于target的时候可以一直选这个数,然后往下递归也是和上面情况一样。这里有个细节要注意,当递归回去的时候,不要直接把path最后一个位置pop掉,而是等到这个数所有情况都选完了然后在pop掉path最后一个元素,因为这个数可以选1次、两次等等,如果选择一次往下走递归回来了你pop掉了,下一次path.push_back()就要放两个这个数,因为我们不先pop,等到最后这个数所有情况搞完返回上一层我们在把前面加入的所有这个数pop掉。

在这里插入图片描述

class Solution {vector<vector<int>> ret;vector<int> path;int aim;
public:vector<vector<int>> combinationSum(vector<int>& candidates, int target) {aim=target;dfs(candidates,0,0);return ret;}void dfs(vector<int>& candidates,int pos,int sum){if(sum == aim){ret.push_back(path);return;}if(sum > aim || pos == candidates.size()) return;// 枚举个数for(int k = 0; k * candidates[pos] + sum <= aim; k++){if(k) path.push_back(candidates[pos]);dfs(candidates, pos + 1, sum + k * candidates[pos]);}// 恢复现场for(int k=1;k*candidates[pos]+sum <= aim;++k){path.pop_back();}}
};

4.字母大小写全排列

题目链接:784. 字母大小写全排列

题目描述:

在这里插入图片描述
算法原理:

还是画出决策树,写代码。
对于每个字母我们都有两种选择,要么不变,要么变,小写变大写,大写变小写。对于数字我们不管它。其他的还是和前面的题一模一样。可以用全局path,也可以path当参数用。

在这里插入图片描述

class Solution {vector<string> ret;string path;
public:vector<string> letterCasePermutation(string s) {dfs(s,0);return ret;}void dfs(string& s,int pos){if(pos == s.size()){ret.push_back(path);return;}char ch=s[pos];// 不改变path.push_back(ch);dfs(s,pos+1);path.pop_back();// 变if(ch < '0' || ch > '9'){if(islower(ch)) ch-=32;else ch+=32;path.push_back(ch);dfs(s,pos+1);path.pop_back();}}
};

http://www.ppmy.cn/devtools/53670.html

相关文章

MySQL 考证作用

提升个人技能&#xff1a;参加MySQL考证的过程本身就是一个学习和提升的过程。考生需要系统地复习和掌握MySQL的相关知识和技能&#xff0c;这有助于提升个人的专业能力和技术水平。增强就业竞争力&#xff1a;在求职过程中&#xff0c;拥有MySQL认证证书可以作为一个加分项&am…

国际数字影像产业园:致力于园区数字化和智能化的发展

数字化和智能化发展策略 数字化基础设施建设&#xff1a;园区提供高标准的基础设施建设&#xff0c;包括高速网络、数据中心等&#xff0c;为入园企业提供稳定、高效的网络和数据服务。通过数字化技术的应用&#xff0c;实现园区内信息的快速传递和资源的优化配置&#xff0c;…

Transformer学习理解

1.前言 本文介绍当下人工智能领域的基石与核心结构模型——Transformer&#xff0c;为什么说它是基石&#xff0c;因为以ChatGPT为代表的聊 天机器人以及各种有望通向AGI&#xff08;通用人工智能&#xff09;的道路上均在采用的Transformer。 Transformer也是当下NLP任…

SQL Server几种琐

SQL Server 中的锁类型主要包括以下几种&#xff0c;它们用于控制并发访问和数据一致性&#xff1a; 1. 共享锁&#xff08;Shared Lock&#xff0c;S 锁&#xff09;&#xff1a; - 用于读取操作&#xff08;如 SELECT 语句&#xff09;。 - 允许多个事务同时读取同一资…

django学习入门系列之第二点《案例2:用户注册改进》

文章目录 更改提交数据类型提交数据/返回数据到后台界面接收数据总结往期回顾 更改提交数据类型 #methods - 提交方式 #methods [提交的数据类型] #GET - 直接提交 #POST - 藏起来提交 app.route(/register,methods [GET])提交数据/返回数据到后台 <!-- 需要返回什么数…

51单片机STC89C52RC——2.2 独立按键控制LED亮灭Plus

目的 当独立K1按键按一下&#xff08;立即松开&#xff09;&#xff0c;LED D1点亮。再按一下K1&#xff08;立即松开&#xff09;LED D1熄灭。 与前一节《51单片机STC89C52RC——2.1 独立按键控制LED亮灭》当独立K1按键按下时LED D1 点亮&#xff0c;松开D1熄灭 效果不一…

解决使用Jmeter进行测试时出现“302“,‘‘401“等用户未登录的问题

使用 JMeter 压力测试时解决登录问题的两种方法 在使用 JMeter 进行压力测试时&#xff0c;可能会遇程序存在安全验证&#xff0c;必须登录后才能对里面的具体方法进行测试&#xff1a; 如果遇到登录问题&#xff0c;通常是因为 JMeter 无法模拟用户的登录状态&#xff0c;导…