算法系列--递归,回溯,剪枝的综合应用(1)（上）
https://developer.aliyun.com/article/1480870?spm=a2c6h.13148508.setting.14.5f4e4f0e6XewYU
💕"对相爱的人来说，对方的心意，才是最好的房子。"💕
作者：Lvzi
文章主要内容：算法系列–递归,回溯,剪枝的综合应用(1)
大家好,今天为大家带来的是
算法系列--递归,回溯,剪枝的综合应用(1)
代码:
class Solution { // 全局变量 List<List<Integer>> ret; List<Integer> path; public List<List<Integer>> subsets(int[] nums) { ret = new ArrayList<>(); path = new ArrayList<>(); dfs(nums,0); return ret; } public void dfs(int[] nums,int pos) { // 递归出口 if(pos == nums.length) { ret.add(new ArrayList<>(path)); return; } // 选 path.add(nums[pos]); dfs(nums,pos + 1); path.remove(path.size() - 1);// 回溯 // 不选 dfs(nums,pos + 1); } }
这种决策树的遍历类似于二叉树遍历中的后序遍历
第二种决策树
以当前位置的值为起始位置,枚举出后面所有的数字的情况
class Solution { // 全局变量 List<List<Integer>> ret; List<Integer> path; public List<List<Integer>> subsets(int[] nums) { ret = new ArrayList<>(); path = new ArrayList<>(); dfs(nums,0); return ret; } public void dfs(int[] nums,int pos) { // 这个遍历类似于前序遍历 根左右 ret.add(new ArrayList<>(path));// 刚进来的时候path为空 空集也是子集的一种 // 从当前位置一直遍历到结束 for(int i = pos; i < nums.length; i++) { path.add(nums[i]); dfs(nums,i+1); path.remove(path.size() - 1);// 回溯 } } }
这种遍历的方式类似于二叉树遍历中的前序遍历,先打印根节点的值,再去遍历左右子树
总结:
- 画出具体详细的决策树,模拟每一步都是在干啥,明确操作
- 设计代码,具体来说是要设计出需要的全局变量和dfs,设计dfs和我们之前递归过程中设计
函数头,函数体,递归出口一样,这不过这里的逻辑会更加的复杂一点 - 注意细节问题:主要从两个方面考虑
- 剪枝
- 回溯
3.找出所有⼦集的异或总和再求和
链接:
https://leetcode.cn/problems/sum-of-all-subset-xor-totals/
分析:
代码:
class Solution { // 全局变量 int ret; int path; public int subsetXORSum(int[] nums) { dfs(nums,0); return ret; } public void dfs(int[] nums,int pos) { ret += path; for(int i = pos; i < nums.length; i++) { path ^= nums[i]; dfs(nums,i + 1);// 递归下一个位置 path ^= nums[i];// 回溯 } } }
注意这里面利用了^运算的性质,a ^ a = 0
还是那句话,画出决策树一切都好办!!!
四.全排列II
链接:
https://leetcode.cn/problems/permutations-ii/
分析:
相较于全排列I多了个限制条件不能有重复的组合出现,那么只需分析出所有的不合法的情况即可
- 同一层中(同一位置比如选择第一个位置的数),不能选择重复的数字
- 和全排列I一样,不能选择已经使用过的数字
对于2的处理和全排列I的处理方式相同,使用一个布尔类型的check数组标记即可,对于1需要判断出 不合法的数据,首先要和前面的数字相同nums[i] == nums[i - 1],i不能越界i != 0,其次上述两个条件还不能完全判定出是不合法的数据,还必须要保证前一个数字是同一层的,check[i - 1] == false
总结来说就是:
nums[i] == nums[i-1] && 在同一层–>不合法数据–>不能dfsnums[i] == nums[i-1] && 不在同一层–>合法数据–>能dfs
此外,为了保证相同的数据是紧挨着的,还需要进行排序
代码:
class Solution { // 全局变量 List<List<Integer>> ret;// 返回值 List<Integer> path;// 记录搜索路径 boolean[] check;// 标记是否被使用过 public List<List<Integer>> permuteUnique(int[] nums) { ret = new ArrayList<>(); path = new ArrayList<>(); check = new boolean[nums.length]; Arrays.sort(nums); dfs(nums); return ret; } public void dfs(int[] nums) { // 递归出口 if(path.size() == nums.length) { ret.add(new ArrayList<>(path)); return; } // 函数体 for(int i = 0; i < nums.length; i++) { // 剪枝 不合法的数据 if(check[i] == true || (i != 0 && nums[i] == nums[i - 1] && check[i - 1] == false)) { continue; } path.add(nums[i]); check[i] = true; dfs(nums); // 回溯 check[i] = false; path.remove(path.size() - 1); } } }
5.电话号码的字⺟组合
链接:
https://leetcode.cn/problems/letter-combinations-of-a-phone-number/
分析:
每一层所做的事情:
- 枚举出当前数字对应的字符串中所有的字符
设计代码:
1.全局变量
ret:返回值
path
string[] map:映射关系
2.dfs(digits,pos)
pos表示digits中字符的下标
递归出口:
走到最后一个节点的位置
回溯:
删除最后添加的数字
剪枝:无
代码:
class Solution { List<String> ret;// 返回值 StringBuffer path;// 记录搜索路径 String[] map= {"","","abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};// 建立映射关系 public List<String> letterCombinations(String digits) { ret = new ArrayList<>(); path = new StringBuffer(); if(digits.length() == 0) return ret;// 处理为空的情况 dfs(digits,0); return ret; } private void dfs(String digits, int pos) { if(pos == digits.length()) {// 递归出口 ret.add(path.toString()); return; } String s = map[digits.charAt(pos) - '0'];// 获取当前层的字符串 for(int i = 0; i < s.length(); i++) { path.append(s.charAt(i));// 追加字符 dfs(digits, pos + 1); path.deleteCharAt(path.length() - 1);// 回溯 } } }
dfs是往下,是递归,每一层是要做的事情是子问题
