滑动窗口算法
- 回溯算法框架
- 回溯算法运用
图片来源于网络
1. 回溯算法框架
回溯算法，是类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。
回溯算法框架：解决一个回溯问题，实际上就是一个决策树的遍历过程。需要思考3个问题：
- 路径：已经做出的选择。
- 选择列表：当前可以做的选择。
- 结束条件：到达决策树底层，无法再做选择的条件。
回溯算法的代码框架：
result = []
def backtrack(路径, 选择列表):
if 满足结束条件:
result.add(路径)
return
for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择
其核心就是 for 循环里面的递归，在递归调用之前「做选择」，在递归调用之后「撤销选择」。
2. 回溯算法运用
2.1 全排列问题
力扣 46 题如下：
全排列
上面题目，比如给三个数 [1,2,3]，可画出如下决策树：
决策树
其中，上图中标红的 [2] 就是 路径，记录已经做过的选择；[1,3] 就是 选择列表，表示当前可以做出的选择；结束条件 就是遍历到树的底层，在这里是选择列表为空的时候。
定义的 backtrack 函数其实就像一个指针，在这棵树上游走，同时要正确维护每个节点的属性，每当走到树的底层，其「路径」就是一个全排列。如下：
正确维护每个节点的属性
只要在递归之前做出选择，在递归之后撤销刚才的选择，就能正确得到每个节点的选择列表和路径"：
for 选择 in 选择列表:
# 做选择
将该选择从选择列表移除
路径.add(选择)
backtrack(路径, 选择列表)
# 撤销选择
路径.remove(选择)
将该选择再加入选择列表
通过回溯算法框架实现全排列代码如下：
/**
* 全排列：输入一组不重复的数字，返回它们的全排列
* <p>
* 时间复杂度：O(N!)
*/
public List<List<Integer>> permute(int[] nums) {
// 记录「路径」
LinkedList<Integer> track = new LinkedList<>();
backTack(nums, track);
return res;
}
List<List<Integer>> res = new LinkedList<>();
/**
* 路径：记录在 track 中
* 选择列表：nums 中不存在于 track 的那些元素（没有显式记录选择列表，这边通过 nums 和 track 推导出）
* 结束条件：nums 中的元素全都在 track 中出现
*/
void backTack(int[] nums, LinkedList<Integer> track) {
// 触发结束条件
if (track.size() == nums.length) {
res.add(new LinkedList<>(track));
return;
}
for (int i = 0; i < nums.length; i++) {
// 排除不合法的选择
if (track.contains(nums[i])) continue;
// 做选择
track.add(nums[i]);
// 进入下一层决策树
backTack(nums, track);
// 取消选择
track.removeLast();
}
}
小结：不像动态规划存在重叠子问题可以优化，回溯算法就是纯暴力穷举，复杂度一般都很高。
2.2 N 皇后问题
力扣 51 题如下：
皇后问题
注：皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。
这个问题跟全排列问题差不多，决策树的每一层表示棋盘上的每一行；每个节点可以做出的选择是，在该行的任意一列放置一个皇后。
套用回溯算法框架如下：
/**
* N 皇后问题：输入棋盘边长 n，返回所有合法的放置
*/
public List<List<String>> solveNQueens(int n) {
// '.' 表示空，'Q' 表示皇后，初始化空棋盘。
char[][] board = new char[n][n];
for (int i = 0; i < n; i++) {
Arrays.fill(board[i], '.');
}
backtrack(board, 0);
return res2;
}
List<List<String>> res2 = new ArrayList<List<String>>();
/**
* 路径：board 中小于 row 的那些行都已经成功放置了皇后
* 选择列表：第 row 行的所有列都是放置皇后的选择
* 结束条件：row 超过 board 的最后一行
*/
void backtrack(char[][] board, int row) {
// 触发结束条件
if (row == board.length) {
res2.add(convertToList(board));
return;
}
int n = board[0].length;
for (int col = 0; col < n; col++) {
// 排除不合法选择
if (!isValid(board, row, col)) continue;
// 做选择
board[row][col] = 'Q';
// 进入下一行决策
backtrack(board, row + 1);
// 撤销选择
board[row][col] = '.';
}
}
上面部分是主要代码，其中 isValid 函数的实现如下：
/**
* 是否可以在 board[row][col] 放置皇后？
*/
boolean isValid(char[][] board, int row, int col) {
int n = board[0].length;
// 检查列是否有皇后互相冲突
for (int i = 0; i < n; i++) {
if (board[i][col] == 'Q') return false;
}
// 检查右上方是否有皇后互相冲突
for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
if (board[i][j] == 'Q') return false;
}
// 检查左上方是否有皇后互相冲突
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if (board[i][j] == 'Q') return false;
}
return true;
}
/**
* char[][] 转成 List<String>
*/
List<String> convertToList(char[][] board) {
List<String> list = new ArrayList<>();
for (char[] chars : board) {
list.add(new String(chars));
}
return list;
}
小结：回溯算法就是个多叉树的遍历问题，关键就是在前序遍历和后序遍历的位置做一些操作，写 backtrack 函数时，需要维护走过的「路径」和当前可以做的「选择列表」，当触发「结束条件」时，将「路径」记入结果集。
2.3 括号生成
力扣 22 题如下：
括号生成
有关括号问题，有如下两个性质：
-
一个「合法」括号组合的左括号数量一定等于右括号数量。
-
对于一个「合法」的括号字符串组合
p，必然对于任何0 <= i < len(p)都有：子串p[0..i]中左括号的数量>=右括号的数量。
上面题目也可以这么理解，有 2n 个位置，每个位置可以放置字符 ( or )，组成的所有括号组合中，有多少个是合法的？套用回溯算法框架思路如下：
void backtrack(int n, int i, string& track) {
// i 代表当前的位置，共 2n 个位置
// 穷举到最后一个位置了，得到一个长度为 2n 组合
if (i == 2 * n) {
print(track);
return;
}
// 对于每个位置可以是左括号或者右括号两种选择
for choice in ['(', ')'] {
track.push(choice); // 做选择
// 穷举下一个位置
backtrack(n, i + 1, track);
track.pop(choice); // 撤销选择
}
}
显然对于 2n 个位置，分别有 n 个左括号和右括号，这边用 left 记录还可以使用多少个左括号，用 right 记录还可以使用多少个右括号，实现代码如下：
/**
* 括号生成
*/
public List<String> generateParenthesis(int n) {
// 记录所有合法的括号组合
List<String> res = new ArrayList<>();
// 回溯过程中的路径
List<Character> track = new ArrayList<>();
// 可用的左括号和右括号数量初始化为 n
backtrack(n, n, track, res);
return res;
}
/**
* 可用的左括号数量为 left 个，可用的右括号数量为 right 个
*/
void backtrack(int left, int right, List<Character> track, List<String> res) {
// 触发结束条件
if (right < left) return; // 若左括号剩下的多，说明不合法
if (left < 0 || right < 0) return; // 数量小于 0 是不合法的
if (left == 0 && right == 0) {
// 当所有括号都恰好用完时，得到一个合法的括号组合
StringBuilder sb = new StringBuilder();
for (Character c : track) {
sb.append(c);
}
res.add(sb.toString());
return;
}
// 尝试放一个左括号
track.add('('); // 选择
backtrack(left - 1, right, track, res);
track.remove(track.size() - 1); // 撤消选择
// 尝试放一个右括号
track.add(')'); // 选择
backtrack(left, right - 1, track, res);
track.remove(track.size() - 1); // 撤消选择
}
2.4 子集问题
力扣 78 题如下：
子集
上题中返回的解集可看成是如下树的所有节点：
[1 2 3] 返回的解集
套用回溯算法实现如下：
/**
* 子集
*/
public List<List<Integer>> subsets(int[] nums) {
// 记录路径
List<Integer> track = new ArrayList<>();
backtrack(nums, 0, track);
return res4;
}
List<List<Integer>> res4 = new ArrayList<>();
void backtrack(int[] nums, int start, List<Integer> track) {
res4.add(new ArrayList<>(track));
// 注意 i 从 start 开始递增
for (int i = start; i < nums.length; i++) {
// 做选择
track.add(nums[i]);
Log.d("backtrack", "size: " + track.size());
// 回溯
backtrack(nums, i + 1, track);
// 撤销选择
track.remove(track.size() - 1);
}
}
2.5 子集划分问题
力扣 698 题如下：
划分为 k 个相等的子集
上面题目可用看作将 n 个数字分配到 k 个「桶」里，最后这 k 个「桶」里的数字之和要相同。
将 n 个数字分配到 k 个桶里，有两种方案：
-
以这
n个数字的视角，每个数字都要选择进入到k个桶中的某一个。
以数字的视角，选择 k 个桶，递归代码逻辑如下：
// k 个桶（集合），记录每个桶装的数字之和
int[] bucket = new int[k];
// 穷举 nums 中的每个数字
void backtrack(int[] nums, int index) {
// base case
if (index == nums.length) {
return;
}
// 穷举每个桶
for (int i = 0; i < bucket.length; i++) {
// 选择装进第 i 个桶
bucket[i] += nums[index];
// 递归穷举下一个数字的选择
backtrack(nums, index + 1);
// 撤销选择
bucket[i] -= nums[index];
}
}
完善代码如下：
/**
* 划分为k个相等子集 -- 以数字为视角
* 时间复杂度：O(k^n)
*/
public boolean canPartitionKSubsets(int[] nums, int k) {
// 排除一些基本情况
if (k > nums.length) return false;
int sum = 0;
for (int num : nums) sum += num;
if (sum % k != 0) return false;
// 提前对nums数组降序排序，大的数字会先被分配到bucket中，
// 对于之后的数字，bucket[i] + nums[index]会更大，更容易触发剪枝的 if 条件
Arrays.sort(nums);
int i = 0, j = nums.length - 1;
for (; i < j; i++, j--) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
// k 个桶（集合），记录每个桶装的数字之和
int[] bucket = new int[k];
// 理论上每个桶（集合）中数字的和
int target = sum / k;
// 穷举，看看 nums 是否能划分成 k 个和为 target 的子集
return backtrack(nums, bucket, 0, target);
}
/**
* 穷举 nums 中的每个数字
*/
boolean backtrack(int[] nums, int[] bucket, int index, int target) {
// base case
if (index == nums.length) {
// 检查所有桶的数字之和是否都是 target
for (int sum : bucket) {
if (sum != target) {
return false;
}
}
// nums 成功平分成 k 个子集
return true;
}
// 穷举 nums[index] 可能装入的桶
for (int i = 0; i < bucket.length; i++) {
// 剪枝，桶装装满了
if (bucket[i] + nums[index] > target) continue;
//将 nums[index] 装入 bucket[i]
bucket[i] += nums[index];
// 递归穷举下一个数字的选择
if (backtrack(nums, bucket, index + 1, target)) {
return true;
}
// 撤销选择
bucket[i] -= nums[index];
}
// nums[index] 装入哪个桶都不行
return false;
}
- 以这
k个桶的视角，对于每个桶，都要遍历nums中的n个数字，然后选择是否将当前遍历到的数字装进这个桶里。
以桶的视角，需要遍历 nums 中所有数字，决定哪些数字需要装到当前桶中，若当前桶装满了（桶内数字和达到 target），则让下一个桶开始执行第 1 步，实现代码如下：
/**
* 划分为k个相等子集 -- 以桶为视角
* 时间复杂度：O(k*2^n)
*/
public boolean canPartitionKSubsets2(int[] nums, int k) {
// 排除一些基本情况
if (k > nums.length) return false;
int sum = 0;
for (int v : nums) sum += v;
if (sum % k != 0) return false;
boolean[] used = new boolean[nums.length];
int target = sum / k;
// k 号桶初始什么都没装，从 nums[0] 开始做选择
return backtrack(nums, used, 0, 0, k, target);
}
boolean backtrack(int[] nums, boolean[] used, int start, int bucket, int k, int target) {
// base case
if (k == 0) {
// 所有桶都被装满了，而且 nums 一定全部用完了
// 因为 target == sum / k
return true;
}
if (bucket == target) {
// 装满了当前桶，递归穷举下一个桶的选择
// 让下一个桶从 nums[0] 开始选数字
return backtrack(nums, used, 0, 0, k - 1, target);
}
// 从 start 开始向后探查有效的 nums[i] 装入当前桶
for (int i = start; i < nums.length; i++) {
// 剪枝
if (used[i]) continue; // nums[i] 已经被装入别的桶中
if (nums[i] + bucket > target) continue; // 当前桶装不下 nums[i]
// 做选择，将 nums[i] 装入当前桶中
used[i] = true;
bucket += nums[i];
// 递归穷举下一个数字是否装入当前桶
if (backtrack(nums, used, i + 1, bucket, k, target)) return true;
// 撤销选择
used[i] = false;
bucket -= nums[i];
}
// 穷举了所有数字，都无法装满当前桶
return false;
}
2.6 组合问题
力扣 77 题如下：
组合
上面题目中 k 限制了树的高度，n 限制了树的宽度，如下所示：
n = 4, k = 2
这道题和子集问题差不多，套用回溯算法框架代码实现如下：
/**
* 组合
*/
public List<List<Integer>> combine(int n, int k) {
if (k <= 0 || n <= 0) return res5;
// 记录路径
List<Integer> track = new ArrayList<>();
backtrack(n, k, 1, track);
return res5;
}
List<List<Integer>> res5 = new ArrayList<>();
void backtrack(int n, int k, int start, List<Integer> track) {
// 到达树的底部
if (k == track.size()) {
res5.add(new ArrayList<>(track));
return;
}
// 注意 i 从 start 开始递增
for (int i = start; i <= n; i++) {
// 做选择
track.add(i);
backtrack(n, k, i + 1, track);
// 撤销选择
track.remove(track.size() - 1);
}
}
小结：
回溯算法非常简单粗暴，可以认为是一种树的遍历问题，时间复杂度比较高。
排列问题用回溯算法时，使用 contains 方法排除已经选择的数字。
子集问题用回溯算法时，要用 start 排除已选择的数字。
组合问题用回溯算法时，要用 start 排除已选择的数字。
参考链接：
网友评论