番禺建网站,南宁建设网站,杭州做网站小程序多少钱,大数据 做网站流量统计其中标题的深搜#xff0c;回溯#xff0c;剪枝我们之前专题都已经有过学习和了解#xff0c;这里多了两个穷举和暴搜#xff0c;其实意思都差不多#xff0c;穷举就是穷尽力气将所有情况都列举出来#xff0c;暴搜就是暴力地去一个一个情况搜索#xff0c;所以就是全部…其中标题的深搜回溯剪枝我们之前专题都已经有过学习和了解这里多了两个穷举和暴搜其实意思都差不多穷举就是穷尽力气将所有情况都列举出来暴搜就是暴力地去一个一个情况搜索所以就是全部遍历的意思
而实现全部遍历之前我们需要将所有情况以树状来大致画出来这棵树就叫做决策树也就是在上学时数学的某一小节学过的决策树如下图
将123的所有排列情况列举出来 就是填空一样将不同情况画出树
那么这就涉及深搜回溯和剪枝只不过之前是二叉树现在变为了多叉树
但过程都大致差不多只要画出清晰的决策树就可以将决策转化为代码
题目一 思路
先画出决策树就是上面我们举例的决策树 其中我们需要一个全局变量二维数组ret来存储所有排列的情况也是我们要返回的结果集
然后我们还需要一个全局变量一维数组path来记录其中一次的排列情况也就做其中一条路径
然后还需要一个全局变量布尔数组来记录数字的使用情况没使用过为false使用过为true
然后我们就开始遍历但注意我们是深搜dfs不是宽搜bfs即虽然画决策树的时候是先填第一个空123但实际遍历我们是填1之后将1对应的所有情况都搜索完之后再回到2这里即dfs的搜索顺序而不是bfs
结束条件也很好想就是当path的元素个数等于数组元素个数就说明排完了那么就将该path填入结果集ret中但注意path要重新new一个出来不然传的是地址后续搜索其他排列时对path修改会连带着修改之前填入的path即所有path都指向同一个path填入之后还可以用剪枝稍微优化一下因为填就说明全部元素用到了后面的其他元素都没必要再搜索了因为结果都是不可能的
而往下遍历的时候都是for循环数组的所有元素调用布尔数组如果该元素用过就不加没用过就加然后继续往下搜索
碰到结束条件后就该回溯那么就该修改布尔数组和path将该数的布尔值修改为false再删除path的最后一个元素
最后返回ret即可
代码
class Solution {//保存所有全排列的结果集ListListInteger retnew ArrayList();//用于判断该数字是否使用过boolean[] check;//其中一个排列ListInteger pathnew ArrayList();public void dfs(int[] nums){//如果排列元素的个数等于数组元素的个数说明排完了if(path.size()nums.length){//添加该排列情况要new一个新的不然就是传地址ret.add(new ArrayList(path));//剪枝return;}//遍历数组for(int i0;inums.length;i){//如果当前元素没有使用过if(check[i]false){//添加该情况path.add(nums[i]);//标记该元素使用过check[i]true;//选择下一个元素dfs(nums);//回溯该元素修改为没使用check[i]false;//删除该元素path.remove(path.size()-1);}}}public ListListInteger permute(int[] nums) { checknew boolean[nums.length];dfs(nums);return ret;}
}
题目二 思路
还是先画决策树不同的决策树画法有不同的代码但只要决策树画对代码实现了就一定是对的 求子集大概有两种决策树画法
解法1 这种决策树画法就是遍历数组每遍历一个就出现两种决策选或者不选最后叶子结点就是所有的子集
代码1
class Solution {//结果集ListListInteger ret new ArrayList();//其中一个子集ListInteger path new ArrayList();//k表示到数组的哪一个元素了public void dfs(int[] nums, int k) {//如果遍历完数组了if(knums.length){ret.add(new ArrayList(path));return;}//选path.add(nums[k]);dfs(nums,k1);//恢复现场path.remove(path.size()-1);//不选dfs(nums,k1);}public ListListInteger subsets(int[] nums) {dfs(nums, 0);return ret;}
}
解法2 这种决策树的画法就是以子集中的元素个数来进行决策一开始为0个也就是空集然后为1个就是123再然后为2个……其中是否选择以当前元素的位置为标准比如1就找后面的23而2就找后面的3而3就没得找了这样子就能避免出现重复的情况
则每一个结点都是一个结果所以每次dfs的时候都要添加
代码2
class Solution {//结果集ListListInteger ret new ArrayList();//其中一个子集ListInteger path new ArrayList();//k表示到数组的哪一个元素了public void dfs(int[] nums, int k) {//先添加ret.add(new ArrayListInteger(path));//从当前元素开始往后遍历for (int i k; i nums.length; i) {//添加该元素path.add(nums[i]);//再次基础上往后遍历dfs(nums, i 1);//恢复现场path.remove(path.size() - 1);}}public ListListInteger subsets(int[] nums) {dfs(nums, 0);return ret;}
}
但综合来看肯定是解法2更优因为每一个结点都是结果没有多余的浪费而解法1则全部枚举了出来但最后只选择了叶子结点非叶子结点就多余了
总结
解决全排列集合这种需要枚举许多情况并回溯的先画出决策树决策树不唯一只要思路是对的通过代码来实现其中需要注意回溯后要恢复现场最后就是正确的
