回溯算法解题框架
解决一个回溯问题,需要考虑以下三个问题:
- 路径:也就是已经做出的选择
- 选择列表:当前能做的选择
- 结束条件:达到决策树的底层无法在做出选择
代码框架:
1 | result = [] |
核心其实就是for循环里面的递归,在递归调用之前“做出一个选择”,在递归调用之后”撤销选择“。
通过题目来做一些理解吧
明人不说暗话,直接上全排列:
lc46
题目链接:https://leetcode-cn.com/problems/permutations/
这题就是一个很典型的回溯板子
因为这里我们需要撤销一下之前的走过的选项,所以就需要递归前选元素,递归之后再撤销刚才的选择。
直接看一波代码吧:
1 | /** |
lc784
题目链接:https://leetcode-cn.com/problems/letter-case-permutation/
这题其实也是个回溯。
1 | /** |
lc51 n皇后问题
题目链接:https://leetcode-cn.com/problems/n-queens/
规则:有个 N * N 的棋盘,让你放置 N 个皇后,使他们不能互相攻击。
PS: 攻击的规则是皇后可以攻击同一行、同一列、左上左下右上右下四个方向的任意单位。
这个问题本质上是和全排列差不多的,决策树的每一层表示棋盘上的每一行;每个节点都可以做出的选择是,在该行的任意一列放置一个皇后:
先写一波伪代码:
1 | const res = [] |
主要部分的代码其实和全排列差不多,isValid
函数的实现为:
1 | const isvalid = (board, row, col) => { |
lc 水域大小
这题其实是个典型的dfs找联通块的题目,有8个方向:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55/**
* @param {number[][]} land
* @return {number[]}
*/
var pondSizes = function (grid) {
let m = grid.length
if (m === 0) {
return 0
}
let n = grid[0].length
let res = -1
const dfs = (grid, i, j, res) => {
if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] !== 0) {
return
}
grid[i][j] = res
dfs(grid, i + 1, j, res)
dfs(grid, i - 1, j, res)
dfs(grid, i + 1, j + 1, res)
dfs(grid, i + 1, j - 1, res)
dfs(grid, i - 1, j + 1, res)
dfs(grid, i - 1, j - 1, res)
dfs(grid, i, j + 1, res)
dfs(grid, i, j - 1, res)
}
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === 0) {
dfs(grid, i, j, res--)
}
}
}
let hash = new Map()
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] < 0) {
hash.set(grid[i][j], hash.has(grid[i][j]) ? hash.get(grid[i][j]) + 1 : 1)
}
}
}
let ret = []
for (let [key, value] of hash) {
ret.push(value)
}
return ret.sort((a, b) => a - b)
}
// console.log(
// pondSizes([
// [0, 2, 1, 0],
// [0, 1, 0, 1],
// [1, 1, 0, 1],
// [0, 1, 0, 1],
// ]),
// )