网站功能需求文档,佛山 做网站公司有哪些,徐州手工活外发加工网,激励案例网站制作穷举vs暴搜vs深搜vs回溯vs剪枝 1.全排列2.子集 点赞#x1f44d;#x1f44d;收藏#x1f31f;#x1f31f;关注#x1f496;#x1f496; 你的支持是对我最大的鼓励#xff0c;我们一起努力吧!#x1f603;#x1f603; 管他什么深搜、回溯还是剪枝#xff0c;画出决… 穷举vs暴搜vs深搜vs回溯vs剪枝 1.全排列2.子集 点赞收藏关注 你的支持是对我最大的鼓励我们一起努力吧! 管他什么深搜、回溯还是剪枝画出决策树就完事了~~~
1.全排列
题目链接46. 全排列
题目描述 算法原理
其实这道题本身是一个穷举(枚举)的题3个数你可以三层for循环但是如果10个数100个数呢对于数多的显然不合适此时我们就需要借助递归把所有情况都枚举出来。
解决回溯的步骤
画出决策树越详细越好设计代码 全局变量 dfs函数 细节问题 1.画出决策树 就是在暴力枚举这道题过程中如何不重不漏的把所有情况枚举到就是把自己的想想法按照树的样子画下来。
第一次选择可以直接选123中任何一个接下来每次选择都是从123中选。但是此时你会发现比如第一次选1下一次还选1就会有重复的情况因此这个1我们是要把它剪掉的不考虑有1的情况。第二次选择假设选择的是2在往下选择就还是有123但是此时剪掉的应该更多12不能选只能选3所有最终这条分支就是123同理其他也是这样选出。
决策树画的越详细越好就是把每一步都画出来这样你就会发现每一个节点干的事情都是一样的都是枚举整个数组。无非就是一些分支被我们剪掉。当一直在干同一件事情的时候我们决策树就画成功了因为可以改成递归的代码。 2.设计代码 1.全局变量 全局变量就看这个递归需要什么东西和以及最终要返回什么东西。
全局变量的使用仁者见仁智者见智也可以把全局变量换成参数在递归函数中传递。看个人选择不过还是建议使用全局变量
首先来递归要返回的二维数组再来一个把每次选择都要记录的path。 当path.size() nums.size() 说明已经找到一个符合的组合此时把path放到ret里然后回溯 注意要 恢复现场。在说这个之前我们要说一说这个剪枝的事情。 剪枝怎么解决就是如果避免下一次选择重复的数字。 此时我们也需要一个数组弄一个bool 类型的数组。来判断一下该条路径下的数是否已经被使用过了。bool数组中记录nums数组中的数字是否已经被使用过。 check[0] 对应 1 check[1] 对应 2 check[2] 对应3check初始化都为false只有对应数字被使用了 check[i]true说明这个数字已经被使用过了下一次就不要选这个数字了。 2.dfs函数 仅需关心某一个节点在干什么事情。
3.细节问题 回溯 当我要回去的时候需要把这个3干掉就是向上回去把path最后一个元素干掉但是别忘记了check也是一个全局的 你用3的时候会把check对应位置置为true那你向上返回这个3你都不用了是不是要把3复原啊。
干掉 path 最后一个元素修改 check 数组
剪枝 这里前面说过。
递归出口 遇到叶子节点的时候直接添加结果。不用在到空了。
这样的题一定是决策树画出来是最重要的第二步设计代码你想到哪一点写那一点都可以。
class Solution {vectorvectorint ret;vectorint path;bool check[7]{false};
public:vectorvectorint permute(vectorint nums) {dfs(nums);return ret;}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);//返回之后也可以 回溯 --- 恢复现场 建立返回之后check[i]false;path.pop_back(); }}}
};注意一定是决策树越详细后面代码设计越轻松代码设计考虑一下全局变量、dfs函数、细节问题。
2.子集
题目链接78. 子集
题目描述 算法原理
这里我们采用两种策略来解决这个问题虽然是两种策略但都是深搜所以我们的思考方式是一样的。
解法一
画出决策树设计代码 全局变量 dfs 细节回溯、剪枝、递归出口
首先画决策树我们想想如何能够把所有子集不重不漏全部枚举出来。我们从子集定义出发子集是这个数组里面选or不选某些数形成新的集合就是它的子集。因此我们就单独盯着数组中每个数字考虑选or不选来画出我们的决策树。 此时所有叶子节点就是数组所有不重复的子集。
现在我们仅需把这颗决策树转换成代码就可以了。之前的题无非就是直接把树画好给我们了现在是要我们自己画一颗树。
既然叶子节点是我们的结果因此我们需要两个全局变量一个二维数组ret一个一维数组pathpath把每次选or不选路径记录下来然后ret把path记录下来。这道题我们并不需要剪枝。
dfs函数我们就盯着某一个位置在干什么。比如绿圈的位置因为上面已经选过了所以要需要考虑这一次的数选or不选所以dfs不仅要这个nums还要告诉我你当前选到了那个位置dfs(numspos) 选就加入到path里然后dfs(numspos1)下一层 不选直接 dfs(numspos1)下一层 细节问题回溯要恢复现场因此我们在选的这条路径在递归返回之后把path最后一个位置pop掉剪枝我们这里没有。递归出口当posnums.size()的时候把path放到ret里然后返回即可。
class Solution {vectorvectorint ret;vectorint path;
public:vectorvectorint subsets(vectorint nums) {dfs(nums,0);return ret;}void dfs(vectorint nums,int pos){if(pos nums.size()){ret.push_back(path);return;}// 选path.push_back(nums[pos]);dfs(nums,pos1);path.pop_back(); // 恢复现场// 不选dfs(nums,pos1);}
};解法二 也是上面一样的步骤
画出决策树设计代码 全局变量 dfs 细节回溯、剪枝、递归出口
这里我们换一种思考方式当我们选的子集是没有元素、只有一个元素、只有两个元素、只有三个元素等等。前面的是盯着某一个数选or不选现在我们直接看看最终要的子集要么没有要么一个元素要么两个元素要么三个元素等等从小到大去选。并且每次是从这个被选的数的后面再次选。并且每一个节点都是我们想要的结果。 你会发现我们这种解法比上面少了很多没有必要的情况。
全局变量还是上面那两个dfs函数 从当前节点位置开始向后枚举所以也要知道当前位置 dfs(numspos)。for(int ipos;inums.size();i) 把路径上的节点放入path然后递归到下一层dfs(numspos1)当递归返回收把path最后一个位置pop掉。 回溯也要恢复现场把path最后一个位置pop掉这里我们不用剪枝递归出口每次进入递归函数后先把path先放到ret里。然后也不需要出口循环条件不满足就出去了。
class Solution {vectorvectorint ret;vectorint path;
public:vectorvectorint subsets(vectorint nums) {dfs(nums,0);return ret;}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(); // 恢复现场}}
};
