0%

常见的 BFS 模板题目

bfs解题框架

参考文章

算法框架

bfs题目出现的常见场景:问题的本质实际上是在一张图里面找从 start 到 end 的最近距离

广义的描述有很多的题目变形:例如走迷宫、有的格子不能走、起点到终点的最短路?有瞬间传送的门?

参考 labuladong算法笔记是可以有一个bfs的算法迭代框架的:

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
int bfs (Node start, Node target) {
Queue<Node> q;
// 用来去重的数据结构
Set<Node> visited;
// 起点进入队列
q.offer(start);
// 标记
visited.add(start);
int step = 0;

while (q not empty) {
int sz = q.size();
// 将队列中的节点四周扩散
for (int i = 0;i<sz;i++) {
Node cur = q.poll()
// 边界条件,如果这个点到了终点,就返回路径的值
if (cur === target) {
return step;
}
// 不满足则将周围的点加到队列里面来
for (Node x in cur.adj()) {
if (x not in visited) {
q.offer(x);
visited.add(x);
}
}
}
}
// 每次走完之后更新一下路径
step ++;
}

里面 cur.adj() 就代表cur附近相邻的节点;visited的作用主要是为了防止走回头路,但一般的二叉树结构,没有子节点到父节点到指针,不会走回头路就不需要visited

下面可以找一些具体的题目来使用这些框架:

lc#111

题目链接

这题因为是找最小的深度其实也是可以用bfs板子写的,其实还挺简单的hhh

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
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var minDepth = function(root) {
if (!root) {
return 0
}
let queue = []
let visited = new Map()
let step = 1;
queue.push(root)
while(queue.length !== 0) {
let sz = queue.length
for (let i = 0;i<sz;i++) {
let cur = queue.shift()
if (!cur.left && !cur.right) {
return step
}
cur.left && queue.push(cur.left)
cur.right && queue.push(cur.right)
}
step ++
}
return step;
};

lc#752

题目链接

这题虽然看上去不是很容易发现是bfs(就我自己而言不知道怎么去搜索),实际上我们以’0000’为起点去进行一个搜索,把所有的情况用bfs搜一遍,就可以了,具体思路可以参考代码里面的情况:

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
/**
* @param {string[]} deadends
* @param {string} target
* @return {number}
*/
var openLock = function (deadends, target) {
// 处理锁的情况
const plusOne = (str, index) => {
let s = str.split('')
if (s[index] === '9') {
s[index] = '0'
} else {
s[index] = String.fromCharCode(s[index].charCodeAt() + 1)
}
return s.join('')
}

const minusOne = (str, index) => {
let s = str.split('')
if (s[index] === '0') {
s[index] = '9'
} else {
s[index] = String.fromCharCode(s[index].charCodeAt() - 1)
}
return s.join('')
}
// 记录边界值
let deads = new Map()
for (let item of deadends) {
deads.set(item, deads.get(item) ? deads.get(item) + 1 : 1)
}
// 记录已经走过的密码情况
let visited = new Map()
let queue = []
let step = 0
queue.push('0000')
visited.set('0000', 1)
while (queue.length !== 0) {
let sz = queue.length
for (let i = 0; i < sz; i++) {
let cur = queue.shift()
// 走重了
if (deads.has(cur)) {
continue
}
// 到了
if (cur === target) {
return step
}
// 处理一下节点的遍历
// 这题不好处理的地方就在这个地方。开始没有想到可以这样去访问周围的情况
for (let j = 0; j < 4; j++) {
let up = plusOne(cur, j)
if (!visited.has(up)) {
queue.push(up)
visited.set(up, 1)
}
let down = minusOne(cur, j)
if (!visited.has(down)) {
queue.push(down)
visited.set(down, 1)
}
}
}
// console.log(queue);
step++
}
return -1
}

// console.log(openLock(['0201', '0101', '0102', '1212', '2002'], '0202'))

lc279

这题其实可以dp,也可以bfs,因为就相当于要找到一个类似于最短路径的概念,这里也要明白bfs这个过程是怎么进行的(这里还是使用bfs模版来搞一搞):

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
/**
* @param {number} n
* @return {number}
*/
var numSquares = function (n) {
let queue = []
let visited = new Map()
queue.push(n)
visited.set(n, 1)
let step = 0
while (queue.length) {
let sz = queue.length
for (let i = 0; i < sz; i++) {
let cur = queue.shift()
// 处理一下下一轮队列的情况
for (let j = 1; j * j <= cur; j++) {
let now = cur - j * j
if (now === 0) {
step++
return step
}
// 如果now这个值没有被标记,送进下一轮bfs
if (!visited.has(now)) {
queue.push(now)
visited.set(now, 1)
}
}
}
step++
}
return 0
}

console.log(numSquares(12))

lc1284 转化为全零矩阵的最少反转次数

这题每次bfs存每次数组转换之后的状态就行了。

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
/**
* @param {number[][]} mat
* @return {number}
*/
// 反转指的是能够将 0-> 1 1-> 0 每次反转相邻边上的单元格也被翻转
// 求最小反转次数
/**
* 1,1,1
* 1,0,1 ->
* 0 0 0
*/
// 直接使用js的map来对每一次对状态进行一个存储

var minFlips = function (mat) {
let m = mat.length,
n = mat[0].length
let queue = []
let visited = new Map()
let first = JSON.stringify(mat)
let step = 0
queue.push(first)
visited.set(first, 1)
const judge = (arr) => {
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (arr[i][j] !== 0) {
return false
}
}
}
return true
}
// 用来改变单元格当前的值
const changeArr = (arr, i, j) => {
if (arr[i][j] === 0) {
arr[i][j] = 1
} else {
arr[i][j] = 0
}
return arr
}
// 改变单元格及其周围单元格的值
const change = (arr, i, j) => {
arr = changeArr(arr, i, j)
let dir = [
[0, 1],
[0, -1],
[-1, 0],
[1, 0],
]
for (let k = 0; k < 4; k++) {
if (
i + dir[k][0] < 0 ||
i + dir[k][0] >= m ||
j + dir[k][1] < 0 ||
j + dir[k][1] >= n
) {
continue
} else {
arr = changeArr(arr, i + dir[k][0], j + dir[k][1])
}
}
return arr
}
// bfs直接搜一波的
while (queue.length) {
let sz = queue.length
for (let i = 0; i < sz; i++) {
let item = queue.shift()
let item2 = JSON.parse(item)
// bfs的终点条件
if (judge(item2)) {
return step
}
// 直接去搜所有的状态,然后放进去队列里面
for (let x = 0; x < m; x++) {
for (let y = 0; y < n; y++) {
item3 = JSON.parse(JSON.stringify(item2))
let changeArr = JSON.stringify(change(item3, x, y))
if (visited.has(changeArr)) {
continue
} else {
queue.push(changeArr)
visited.set(changeArr, 1)
}
}
}
}
step++
}
return -1
}

lc301 删除无效的括号

这题也是一个很有意思的bfs,其实想法挺简单的,每一层都只删一个括号,然后往下去找,直到某一层有结果了直接把这一层符合条件的结果收集起来输出出去就可以了。

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
56
57
58
59
60
61
62
63
64
65
/**
* @param {string} s
* @return {string[]}
*/
// 删除
var removeInvalidParentheses = function (s) {
const isvalid = (str) => {
str = str.split('')
let stack = []
for (let item of str) {
if (item === '(') {
stack.push(item)
} else if(item === ')'){
let item1 = stack.pop()
if (item1 !== '(') {
return false
}
}
}
return stack.length === 0
}
let res = []
let queue = []
let visited = new Map()
// 直接遍历去删
visited.set(s, 1)
queue.push(s)
let step = 0
while (queue.length) {
let sz = queue.length
for (let i = 0; i < sz; i++) {
let item = queue.shift()
if (isvalid(item) && item) {
res.push(item)
}
for (let k = 0; k < item.length; k++) {
let item3 = ''
// 只用删括号
if (item[k] === '(' || item[k] === ')') {
if (k === 0) {
item3 = item.slice(1)
} else if (k === item.length - 1) {
item3 = item.slice(0, k)
} else {
item3 = item.slice(0, k) + item.slice(k + 1)
}
}
if (visited.has(item3)) {
continue
} else {
visited.set(item3, 1)
queue.push(item3)
}
}
}
step++
if (res.length !== 0) {
return res
}
}
return ['']
}

// console.log(removeInvalidParentheses('()())()'))
// console.log(removeInvalidParentheses("(a)())()"))

但是注意里面字符还有不是括号的,做好特判就行了。