算法系列--递归,回溯,剪枝的综合应用(2)（上）
https://developer.aliyun.com/article/1480876?spm=a2c6h.13148508.setting.14.5f4e4f0eSGWvhm
💕"对相爱的人来说，对方的心意，才是最好的房子。"💕
作者：Lvzi
文章主要内容：算法系列–递归,回溯,剪枝的综合应用(2)
大家好,今天为大家带来的是
算法系列--递归,回溯,剪枝的综合应用(2)
4.字⺟⼤⼩写全排列
题目链接
题目描述
784. 字母大小写全排列
给定一个字符串 s，通过将字符串 s 中的每个字母转变大小写，我们可以获得一个新的字符串。
返回所有可能得到的字符串集合。以任意顺序返回输出。
示例:
- 输入：s = “a1b2”
输出：[“a1b2”, “a1B2”, “A1b2”, “A1B2”] - 输入: s = “3z4”
输出: [“3z4”,“3Z4”]
提示:
- 1 <= s.length <= 12
s由小写英文字母、大写英文字母和数字组成
解题思路
这道题可以使用回溯算法来解决。我们可以逐个遍历字符串中的每个字符，然后对于每个字符有两种选择：保持原大小写或者转换大小写。通过递归实现所有可能的组合。
代码实现（Java）
class Solution { List<String> ret; StringBuffer path; public List<String> letterCasePermutation(String s) { ret = new ArrayList<>(); path = new StringBuffer(); dfs(s,0); return ret; } private void dfs(String s, int pos) { if(pos == s.length()) { ret.add(path.toString()); return; } // 不改变 char ch = s.charAt(pos); path.append(ch); dfs(s, pos + 1); path.deleteCharAt(path.length() - 1); // 改变(非数字字符) if(ch < '0' || ch > '9') { char tmp = change(ch); path.append(tmp); dfs(s, pos + 1); path.deleteCharAt(path.length() - 1); } } private char change(char ch) { if(ch >= 'a' && ch <= 'z') return ch -= 32; else return ch += 32; } }
5.优美的排列
题目链接
题目描述
526. 优美的排列
假设有从 1 到 n 的 n 个整数。用这些整数构造一个数组 perm（下标从 1 开始），只要满足下述条件之一，该数组就是一个优美的排列：
- perm[i] 能够被 i 整除
- i 能够被 perm[i] 整除
给你一个整数 n ，返回可以构造的优美排列的数量。
示例:
输入：n = 2
输出：2
解释：
- 第 1 个优美的排列是 [1,2]：
- perm[1] = 1 能被 i = 1 整除
- perm[2] = 2 能被 i = 2 整除
- 第 2 个优美的排列是 [2,1]:
- perm[1] = 2 能被 i = 1 整除
- i = 2 能被 perm[2] = 1 整除
解题思路
这道题可以使用回溯算法来解决。我们可以尝试将数字填充到数组的每个位置上，同时检查当前位置是否满足条件。如果满足条件，继续递归处理下一个位置；否则，回溯到上一个位置重新尝试其他数字。
check[i]:用于标记数字是否被使用过ret:返回值
代码实现（Java）
class Solution { int ret;// 返回值 boolean[] check;// 用于标记已经使用过的数字 public int countArrangement(int n) { check = new boolean[n + 1]; dfs(1,n); return ret; } private void dfs(int pos, int n) {// pos是下标 if(pos == n + 1) {// 递归出口 ret += 1; return; } for(int i = 1; i <= n; i++) { if(check[i] == false && (pos % i == 0 || i % pos == 0)) { check[i] = true;// 将使用过的数字标记 dfs(pos + 1, n);// 递归下一个位置 check[i] = false;// 回溯 } } } }
在这段代码中：
pos表示当前递归到的位置，也就是在填充数组时当前正在考虑的位置。i则表示尝试填充到当前位置pos上的数字。
具体来说：
pos从1开始，代表数组中的位置，递归函数会尝试将数字填充到这些位置上。i从1到n，代表可以填充到当前位置的数字，即数组中的元素。
6. 组合
题目链接
题目描述
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按任何顺序返回答案。
示例 1：
输入：n = 4, k = 2
输出：
[ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
示例 2：
输入：n = 1, k = 1
输出：[[1]]
提示：
- 1 <= n <= 20
- 1 <= k <= n
分析:
代码:
class Solution { List<List<Integer>> ret; List<Integer> path; int k, n; public List<List<Integer>> combine(int nn, int kk) { n = nn; k = kk; ret = new ArrayList<>(); path = new ArrayList<>(); dfs(1); return ret; } private void dfs(int start) { if(path.size() == k) { ret.add(new ArrayList<>(path)); return; } for(int i = start; i <= n; i++) { path.add(i);// 添加当前数字 dfs(i + 1);// 递归下一个数字 path.remove(path.size() - 1);// 回溯 } } }
总结:
- 对于递归回溯这样的问题,一定要把决策树画的详细,要明确每一步的目的是什么,是根据什么进行递归的
对于这种递归回溯剪枝综合应用的题目来说,其分析思路是比较固定的:
- 画出详细的决策树(越详细越好,把所有的情况都写出来)
- 分析每一个子问题都是在干啥
- 设计全局变量和
dfs(其实dfs是这种问题最难的一步,dfs的设计本质上是一个递归的问题),dfs的设计包括三个方面:函数头,函数体,递归出口 - 考虑回溯和剪枝
