💕"对相爱的人来说，对方的心意，才是最好的房子。"💕
作者：Lvzi
文章主要内容：算法系列–递归,回溯,剪枝的综合应用(1)
大家好,今天为大家带来的是
算法系列--递归,回溯,剪枝的综合应用(1)
1.全排列(重点)
链接:
https://leetcode.cn/problems/permutations/description/
分析:
1.画出决策树
所谓的决策树就是我们小时候学排列画的树状图,通过一个树枚举出所有的情况
画出决策树之后,分析每一层干的事情是否相同(一般都是相同的),对于本题,每一层干的事可以总结为
枚举出所有符合条件的排列情况
注意:决策树画的越详细越好(包括所有不符合条件的情况也画出来),有助于我们后面设计代码
2.设计代码
设计代码主要从两个方面考虑
- 全局变量
- dfs函数
1.全局变量
模拟决策的过程,想想需要哪些变量,首先题目要求的返回值是一个二维数组,所以需要设计一个ret作为返回值,当我们在枚举出所有的情况时,要考虑到枚举的数字是否被使用,如果被使用就不能被枚举,所以要标记搜索路径上数字的使用情况,所以要创建一个布尔类型的数组,接着当我们走到叶子结点时,需要保存当前排列的情况,一共就三个数字,所以需要使用一个数组进行保存,接着当从叶子结点向上返回时,我们需要舍弃掉数组中最后一个数字,这个操作比较简单,可以直接对数组进行变动即可
- List ret: 最后的返回值,用于记录所有排列情况
- List path: 用于记录每一次dfs的结果
- boolean[] check : 用于标记搜索过程中数字的使用情况
2.dfs函数
和递归相同,dfs函数的设计我们只需要关注某一个子问题的具体操作即可
把数组中所有的数都枚举一遍,只要没有用过,就添加到path后面
3.细节问题
- 剪枝:在check中被标记为true,就进行剪枝
- 回溯:如图
- 递归出口:当path中元素的数目和nums中元素的数目相同时,递归结束,将path中的所有元素添加到ret之中
4.代码实现
class Solution { // 全局变量 List<List<Integer>> ret;// 返回值 List<Integer> path;// 记录搜索路径 boolean[] check;// 标记是否被使用过 public List<List<Integer>> permute(int[] nums) { ret = new ArrayList<>(); path = new ArrayList<>(); check = new boolean[nums.length]; dfs(nums); return ret; } public void dfs(int[] nums) { // 递归出口 if(nums.length == path.size()) { ret.add(new ArrayList<>(path)); return; } // 函数体 for(int i = 0; i < nums.length; i++) { if(check[i] == false) { path.add(nums[i]); check[i] = true; dfs(nums); // 回溯 check[i] = false; path.remove(path.size() - 1); } } } }
为什么不是ret.add(path);
2.⼦集
链接:
https://leetcode.cn/problems/subsets/description/
分析:
画决策树:
根据定义选或者不选当前数
每一层都在干啥
分别枚举出选当前数字选和不选当前数的所有情况
设计代码:
全局变量:模拟整个过程,需要两个变量
- ret:接收每次搜索的结果,是最终的返回值
- path: 表示搜索路径的结果
dfs: 需要一个数组和当前的位置(下标),因为我需要知道当前的数是谁
细节问题:
- 剪枝:不需要
- 回溯:只有当选择
选当前数的情况时,在返回的时候需要删除这个数 - 递归出口:当pos走到
n.length时表示数组遍历完毕,结束递归,将path添加进ret之中
算法系列--递归,回溯,剪枝的综合应用(1)（下）https://developer.aliyun.com/article/1480874?spm=a2c6h.13148508.setting.17.352e4f0en4xYH1
