BFS
# 133. 克隆图 (opens new window)
类似题型：138. 随机链表的复制 (opens new window)
哈希表中 kv存放 原图和克隆图节点；
队列中存放下一层节点；
class Solution {
public Node cloneGraph(Node node) {
if(node == null){
return node;
}
//key原图节点，val克隆图节点
HashMap<Node,Node> vis = new HashMap<>();
Queue<Node> que = new LinkedList<>();
que.offer(node);
vis.put(node,new Node(node.val,new ArrayList()));
while(!que.isEmpty()){
Node cur = que.poll();
for(Node neighbor:cur.neighbors){
if(!vis.containsKey(neighbor)){
vis.put(neighbor,new Node(neighbor.val,new ArrayList()));
que.add(neighbor);
}
vis.get(cur).neighbors.add(vis.get(neighbor));
}
}
return vis.get(node);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 841. 钥匙和房间 (opens new window)
计算层数；
class Solution {
public boolean canVisitAllRooms(List<List<Integer>> rooms) {
int n = rooms.size();
int ans = 0;
boolean[] vis = new boolean[n];
Queue<Integer> que = new LinkedList<>();
vis[0] = true;
que.offer(0);
while(!que.isEmpty()){
int i = que.poll();
ans++;
for(int key:rooms.get(i)){
if(!vis[key]){
vis[key] = true;
que.offer(key);
}
}
}
return ans == n;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 542. 01 矩阵 (opens new window)
class Solution {
int[][] dirs = new int[][]{{1,0},{-1,0},{0,-1},{0,1}};
public int[][] updateMatrix(int[][] mat) {
int m = mat.length;
int n = mat[0].length;
int[][] res = new int[m][n];
boolean[][] vis = new boolean[m][n];
Queue<int[]> que = new LinkedList<>();
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(mat[i][j]==0){
que.offer(new int[]{i,j});
vis[i][j] = true;
}
}
}
while(!que.isEmpty()){
var cur = que.poll();
int x = cur[0];
int y = cur[1];
for(var dir:dirs){
int nx = x+dir[0];
int ny = y+dir[1];
if(nx>=0&&nx<m&&ny>=0&&ny<n && !vis[nx][ny]){
res[nx][ny] = res[x][y]+1;
que.offer(new int[]{nx,ny});
vis[nx][ny] = true;
}
}
}
return res;
}
}
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
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
# 994. 腐烂的橘子 (opens new window)
class Solution {
int[][] dirs = new int[][]{{1,0},{-1,0},{0,-1},{0,1}};
public int orangesRotting(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
Queue<int[]> que = new LinkedList<>();
int cnt = 0;//新鲜橘子
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(grid[i][j]==1)
cnt++;
if(grid[i][j]==2)
que.add(new int[]{i,j});
}
}
int ret = 0;
while(cnt>0 && !que.isEmpty()){
ret++;
int size = que.size();
for(int k=0;k<size;k++){
int[] node = que.poll();
int x = node[0];
int y = node[1];
for(int[] dir:dirs){
int dx = x+dir[0];
int dy = y+dir[1];
if(dx>=0&&dx<m&&dy>=0&&dy<n && grid[dx][dy]==1){
grid[dx][dy] = 2;
cnt--;
que.add(new int[]{dx,dy});
}
}
}
}
return cnt>0?-1:ret;
}
}
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
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
# 675. 为高尔夫比赛砍树 (opens new window)
# 1926. 迷宫中离入口最近的出口 (opens new window)
class Solution {
int[][] dirs = new int[][]{{1,0},{0,1},{-1,0},{0,-1}};
public int nearestExit(char[][] maze, int[] entrance) {
int m = maze.length;
int n = maze[0].length;
int i = entrance[0];
int j = entrance[1];
Queue<int[]> que = new LinkedList<>();
que.offer(new int[]{i,j});
boolean[][] vis = new boolean[m][n];
vis[i][j] = true;
int step = 0;
while(!que.isEmpty()){
int len = que.size();
while(len-->0){
var cur = que.poll();
int x = cur[0];
int y = cur[1];
if(!(x==i&&y==j) && (x==m-1||y==n-1||x==0||y==0)){
return step;
}
for(int[] dir:dirs){
int nx = x+dir[0];
int ny = y+dir[1];
if(nx>=0&&nx<m&&ny>=0&&ny<n && !vis[nx][ny] && maze[nx][ny]=='.'){
que.offer(new int[]{nx,ny});
vis[nx][ny] = true;
}
}
}
step++;
}
return -1;
}
}
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
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
# 934. 最短的桥 (opens new window)
# 1091. 二进制矩阵中的最短路径 (opens new window)
# LCP 41. 黑白翻转棋 (opens new window)
# 863. 二叉树中所有距离为 K 的结点 (opens new window)
# 1306. 跳跃游戏 III (opens new window)
方法一：BFS
class Solution {
public boolean canReach(int[] arr, int start) {
if(arr[start]==0)
return true;
int n = arr.length;
Queue<Integer> que = new LinkedList<>();
que.offer(start);
boolean[] vis = new boolean[n];
vis[start] = true;
while(!que.isEmpty()){
int cur = que.poll();
if(arr[cur]==0)
return true;
int nxt1 = cur+arr[cur];
if(nxt1<n && !vis[nxt1]){
que.offer(nxt1);
vis[nxt1] = true;
}
int nxt2 = cur-arr[cur];
if(nxt2>=0 && !vis[nxt2]){
que.offer(nxt2);
vis[nxt2] = true;
}
}
return false;
}
}
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
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
方法二：DFS
class Solution {
boolean[] vis;
int n;
public boolean canReach(int[] arr, int start) {
this.n = arr.length;
this.vis = new boolean[n];
return dfs(arr,start);
}
boolean dfs(int[] arr,int start){
if(start<0 || start>=n || vis[start])
return false;
if(arr[start]==0)
return true;
vis[start] = true;
return dfs(arr,start+arr[start]) || dfs(arr,start-arr[start]);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 433. 最小基因变化 (opens new window)
class Solution {
public int minMutation(String start, String end, String[] bank) {
char[] cs = new char[]{'A','C','G','T'};
Set<String> bankSet = new HashSet<>();
for(String s:bank){
bankSet.add(s);
}
Set<String> vis = new HashSet<>();
Queue<String> que = new LinkedList<>();
que.offer(start);
vis.add(start);
int step = -1;
while(!que.isEmpty()){
step++;
int size = que.size();
for(int i=0;i<size;i++){
String cur = que.poll();
if(cur.equals(end))
return step;
for(char c:cs){
char[] arr = cur.toCharArray();
for(int j=0;j<arr.length;j++){
char tmp = arr[j];
arr[j] = c;
String str = new String(arr);
if(bankSet.contains(str) && !vis.contains(str)){
que.offer(str);
vis.add(str);
}
arr[j] = tmp;
}
}
}
}
return -1;
}
}
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
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
# 127. 单词接龙 (opens new window)
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
if(!wordList.contains(endWord))
return 0;
boolean[] vis = new boolean[wordList.size()];
int idx = wordList.indexOf(beginWord);
if(idx!=-1){
vis[idx] = true;
}
Queue<String> que = new LinkedList<>();
que.offer(beginWord);
int cnt = 0;
while(!que.isEmpty()){
int size = que.size();
cnt++;
while(size-->0){
String cur = que.poll();
for(int i=0;i<wordList.size();i++){
if(vis[i])
continue ;
String s = wordList.get(i);
if(!f(cur,s)){
continue ;
}
if(s.equals(endWord))
return cnt+1;
vis[i] = true;
que.offer(s);
}
}
}
return 0;
}
boolean f(String s1,String s2){
if(s1.length()!=s2.length())
return false;
int cnt = 0;
for(int i=0;i<s1.length();i++){
if(s1.charAt(i)!=s2.charAt(i)){
cnt++;
if(cnt>1)
return false;
}
}
return cnt==1;
}
}
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
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