怎么做能打不开漫画网站,做特色创意菜品的网站,国外网络营销,建筑类网站的推荐理由欢迎访问杀马特主页#xff1a;小小杀马特主页呀#xff01; 目录 前言#xff1a;
例题一全排列#xff1a;
1.题目介绍#xff1a;
2.思路汇总#xff1a;
3.代码解答#xff1a;
例题二子集#xff1a;
题目叙述#xff1a;
解法一#xff1a;
1.思路汇总… 欢迎访问杀马特主页小小杀马特主页呀 目录 前言
例题一·全排列
1.题目介绍
2.思路汇总
3.代码解答
例题二·子集
题目叙述
解法一
1.思路汇总
2.代码解答
解法二 1.思路汇总
2.代码解答 文末小总结 前言
本篇采用两道例题来讲解利用枚举元素的方法使用决策树通过递归以及穿插回溯来解答类似此类问题的系列模版操作(涉及全局变量以及引用传参使用需要回溯问题与具体什么时候使用等)。
当我们使用全局变量大都就要手动的回溯了因为它回归到上一层自己不会改变这里既可以选择全局变量又可以选择引用传参但是比如一个递归函数需要使用多个变量这时候引用传参就麻烦了故需要我们使用全局变量了因此视情况而定本篇我们都使用的是全局变量。
例题一·全排列
1.题目介绍 欢迎大家来挑战leetcode原题链接 . - 力扣LeetCode
2.思路汇总 画出决策树然后令dfs函数能帮我们完成此元素位置从其上到末的path都放入ret然后对于这个数组就是要遍历它了由于我们要定义的path是全局遍历故 要考虑回溯复原操作这里就是我们每次往后递归不能出现前面的元素故这里开一个bool类型数组记录一下 一开始是false变成true就是已经出现了故不进行操作继续循环 终止条件当path满了等于nums的size就返回就行了。 思路从下标0开始遍历数组遍历到一个就放入path记录状态然后继续下面递归依次重复 最后肯定会path等于size然后就放入ret然后回溯在上一层完成删除path的back即恢复现场的操作每一次完成一条路线就往回溯最后归到第一次for循环到退出。 决策图解 3.代码解答
class Solution {
public:vectorvectorint ret;vectorint path;bool check[7]{false};//如果换成vector的bool类型只能用原数组指针区间初始化void dfs(vectorint nums){if(path.size()nums.size()){ret.push_back(path);//终止条件return;}for(int i0;inums.size();i){if(check[i]false){//使用后该状态防止重复使用path.push_back(nums[i]);check[i]true;dfs(nums);//回溯恢复现场path.pop_back();check[i]false;}}}vectorvectorint permute(vectorint nums) {dfs(nums);return ret;}}; 例题二·子集 本题采取两种解法解答一种是叶子节点放入ret另一种就是每当递归到一层这一层的path就是要存入ret的结果。
题目叙述 欢迎大家来挑战leetcode原题链接. - 力扣LeetCode
解法一
1.思路汇总 思路枚举元素分为选i位置的数和不选两条路径然后往下递归最后决策树相当于叶子节点的数就是我们要推进ret的这里可以假设dfs递归函数可以帮我们完成从传入 的pos位置一直走到叶子位置的所有分支路径最后的到叶子节点的path都放入ret然后在第一次分别传入它的左支和右支就可以了。 细节注意传入的pos的位置以及回溯的时候path的变化 2.代码解答
class Solution {
public:vectorvectorint ret;vectorint path;
void dfs(vectorint nums,int pos){if(posnums.size()){ret.push_back(path);path.pop_back();//回溯return;}//可分为左支不走右支走//走pos位置的元素右支path.push_back(nums[pos]);dfs(nums,pos1);//不走pos位置的元素左支dfs(nums,pos1);}vectorvectorint subsets(vectorint nums) {dfs(nums,0);return ret;}
解法二
1.思路汇总 思路我们遍历数组放入path并且当递归到下一层遍历的时候就是当前位置的下一个开始所以循环的第一个是pos位置结合每次下一层递归结束回到上一层都会把下一层的 path里面加入的nums[i]删除即回溯保证了每次每当我们进入一次递归第一个就是子集。 细节1·为什么ret添加不在for里面这样的话最后一次递归完成后无法添加最后一次的结果。 2·为什么每次递归函数传参是i1不是pos1呢:这样的话就会导致递归回来的时候走for里的i的时候再次传入pos1又会进行刚才的递归操作了不符合预期。 2.代码解答 void dfs(vectorint nums,int pos){ret.push_back(path);for(int ipos;inums.size();i){path.push_back(nums[i]);dfs(nums,i1);path.pop_back();}}vectorvectorint subsets(vectorint nums) {dfs(nums,0);return ret;}
文末小总结
像这种类型的dfs思路就是首先根据题意采取穷举等方法画出决策树然后根据规则转化成递归代码终止条件递归操作回溯剪枝的判断其次就是合理应用全局变量等
