0%

常见的回溯模板题目

回溯算法解题框架

解决一个回溯问题,需要考虑以下三个问题:

  • 路径:也就是已经做出的选择
  • 选择列表:当前能做的选择
  • 结束条件:达到决策树的底层无法在做出选择

代码框架:

1
2
3
4
5
6
7
8
9
result = []
def backtrap(路径,选择列表):
if 满足结束条件:
result.add(路径)
return
for 选择 in 选择列表:
做选择
backtrap(路径,选择列表)
撤销选择

核心其实就是for循环里面的递归,在递归调用之前“做出一个选择”,在递归调用之后”撤销选择“

通过题目来做一些理解吧

明人不说暗话,直接上全排列:

lc46

题目链接:https://leetcode-cn.com/problems/permutations/

这题就是一个很典型的回溯板子

因为这里我们需要撤销一下之前的走过的选项,所以就需要递归前选元素,递归之后再撤销刚才的选择

直接看一波代码吧:

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
/**
* @param {number[]} nums
* @return {number[][]}
*/
var permute = function(nums) {
let res = []
let temp = []
const dfs = (temp, nums) => {
if (temp.length === nums.length) {
res.push([...temp])
return;
}
for (let item of nums) {
if(temp.includes(item)) {
continue;
}
// 做出选择
temp.push(item)
// 回溯一波
dfs(temp, nums)
// 回溯走完之后把选择的元素pop走
temp.pop()
}
}
dfs([], nums)
return res;
};

lc784

题目链接:https://leetcode-cn.com/problems/letter-case-permutation/

这题其实也是个回溯。

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
/**
* @param {number[]} nums
* @return {number[][]}
*/
/**
* @param {string} S
* @return {string[]}
*/
var letterCasePermutation = function(S) {
let res = []
S = S.split('')
let temp = []
const dfs = (temp, S,index) => {
if(index === S.length) {
res.push(S.join(''))
return;
}
// 如果当前字符是英文字母,那么就进行一波回溯操作
if(('A' <=S[index]&& S[index] <= 'Z') || ('a' <= S[index] && S[index] <='z')) {
S[index] = S[index].toLowerCase()
dfs(temp, S, index + 1)
S[index] = S[index].toUpperCase()
dfs(temp, S, index + 1)
} else {
// 如果是数字,直接去递归就好了
dfs(temp, S, index + 1)
}
}
dfs(temp, S, 0)
return res;
};

lc51 n皇后问题

题目链接:https://leetcode-cn.com/problems/n-queens/

规则:有个 N * N 的棋盘,让你放置 N 个皇后,使他们不能互相攻击。

PS: 攻击的规则是皇后可以攻击同一行、同一列、左上左下右上右下四个方向的任意单位。

这个问题本质上是和全排列差不多的,决策树的每一层表示棋盘上的每一行;每个节点都可以做出的选择是,在该行的任意一列放置一个皇后:

先写一波伪代码:

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
const res = []

const solve = (n) => {
// . 表示空盘,Q表示皇后,初始化空棋盘
for (let i = 0;i<n;i++) {
for (let j = 0;j<n;j++) {
board[i][j] = '.'
}
}
const backtrap = (board, row) => {
// 触发结束条件
if (row === board.length) {
res.push(board)
return
}
let n = board[row].length
for (let col = 0; col < n; col++) {
// 不符合规定的选择直接pass掉
if (!isValid(board, row, col)) {
continue;
}
// 做出选择
board[row][col] = 'Q'
// 进入下一行决策
backtrap(board, row + 1)
// 撤销掉之前的选择
board[row][col] = '.'
}
}
backtrap(board, 0);
return res;
}

主要部分的代码其实和全排列差不多,isValid函数的实现为:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const isvalid = (board, row, col) => {
let n = board.length
// 检查当前列是否有皇后
for(let i = 0;i<n;i++) {
if(board[i][col] === 'Q') {
return false;
}
}
// 检查右上是否有皇后
for (let i = row - 1,j = col + 1;i>=0 && j<n;i--;j++) {
if(board[i][j] === 'Q') {
return false;
}
}
// 检查左上是否有皇后
for (let i = row - 1,j=col - 1;i>=0 && j>=0;i--,j--) {
if(board[i][j] === 'Q') {
return false
}
}
return true
}

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],
// ]),
// )