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
|
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
|
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)
}
}
}
step++
}
return -1
}
|
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
|
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
}
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
|
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
}
while (queue.length) {
let sz = queue.length
for (let i = 0; i < sz; i++) {
let item = queue.shift()
let item2 = JSON.parse(item)
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
|
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 ['']
}
|
但是注意里面字符还有不是括号的，做好特判就行了。