Skip to content

Commit cead194

Browse files
author
Botao Xiao
committed
[Function add]: 1. Add leetcode solutions with tag bfs.
1 parent 0d1ffb0 commit cead194

File tree

5 files changed

+294
-9
lines changed

5 files changed

+294
-9
lines changed

‎leetcode/212. Word Search II.md

Lines changed: 0 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -181,7 +181,6 @@ class Solution {
181181
result.addAll(set);
182182
return result;
183183
}
184-
int[][] dir = new int[][]{{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
185184
private void dfs(char[][] board, Set<String> result, String word, int i, int j, int index, boolean[][] visited){
186185
if(index == word.length() - 1){
187186
result.add(word);

‎leetcode/542. 01 Matrix.md

Lines changed: 149 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,149 @@
1+
## 542. 01 Matrix
2+
3+
### Question
4+
Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell.
5+
The distance between two adjacent cells is 1.
6+
7+
```
8+
Example 1:
9+
Input:
10+
11+
0 0 0
12+
0 1 0
13+
0 0 0
14+
15+
Output:
16+
17+
0 0 0
18+
0 1 0
19+
0 0 0
20+
21+
Example 2:
22+
Input:
23+
24+
0 0 0
25+
0 1 0
26+
1 1 1
27+
28+
Output:
29+
30+
0 0 0
31+
0 1 0
32+
1 2 1
33+
```
34+
35+
Note:
36+
1. The number of elements of the given matrix will not exceed 10,000.
37+
2. There are at least one 0 in the given matrix.
38+
3. The cells are adjacent in only four directions: up, down, left and right.
39+
40+
### Solution
41+
* Method 1: bfs find from all 1s
42+
```Java
43+
class Solution {
44+
private int[][] dir = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
45+
public int[][] updateMatrix(int[][] matrix) {
46+
int height = matrix.length, width = matrix[0].length;
47+
int[][] result = new int[height][width];
48+
for(int i = 0; i < height; i++)
49+
for(int j = 0; j < width; j++)
50+
result[i][j] = 10000;
51+
for(int i = 0; i < height; i++){
52+
for(int j = 0; j < width; j++){
53+
if(matrix[i][j] == 0){
54+
result[i][j] = 0;
55+
continue;
56+
}
57+
LinkedList<int[]> queue = new LinkedList<>();
58+
int dist = -1;
59+
queue.add(new int[]{i, j});
60+
boolean[][] visited = new boolean[height][width];
61+
visited[i][j] = true;
62+
boolean found = false;
63+
while(!queue.isEmpty() && !found){
64+
++dist;
65+
int size = queue.size();
66+
for(int s = 0; s < size; s++){
67+
int[] cur = queue.poll();
68+
int tempRow = 0, tempCol = 0;
69+
for(int d = 0; d < 4; d++){
70+
tempRow = dir[d][0] + cur[0];
71+
tempCol = dir[d][1] + cur[1];
72+
if(tempRow >= 0 && tempRow < height && tempCol >= 0 && tempCol < width && !visited[tempRow][tempCol]){
73+
if(matrix[tempRow][tempCol] == 0 || result[tempRow][tempCol] != 10000){
74+
result[i][j] = Math.min(result[i][j], matrix[tempRow][tempCol] == 0 ? dist + 1: result[tempRow][tempCol] + dist + 1);
75+
found = true;
76+
}
77+
visited[tempRow][tempCol] = true;
78+
queue.add(new int[]{tempRow, tempCol});
79+
}
80+
}
81+
if(found) break;
82+
}
83+
}
84+
}
85+
}
86+
return result;
87+
}
88+
}
89+
```
90+
91+
* Method 2: bfs find from all zeros
92+
```Java
93+
class Solution {
94+
private int[][] dir = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
95+
public int[][] updateMatrix(int[][] matrix) {
96+
int height = matrix.length, width = matrix[0].length;
97+
Queue<int[]> queue = new LinkedList<>();
98+
boolean[][] visited = new boolean[height][width];
99+
for(int i = 0; i < height; i++){
100+
for(int j = 0; j < width; j++){
101+
if(matrix[i][j] == 0){
102+
visited[i][j] = true;
103+
queue.offer(new int[]{i, j});
104+
}
105+
}
106+
}
107+
while(!queue.isEmpty()){
108+
int[] p = queue.poll();
109+
int tempRow = 0, tempCol = 0;
110+
for(int d = 0; d < 4; d++){
111+
tempRow = dir[d][0] + p[0];
112+
tempCol = dir[d][1] + p[1];
113+
if(tempRow >= 0 && tempRow < height && tempCol >= 0 && tempCol < width && !visited[tempRow][tempCol]){
114+
matrix[tempRow][tempCol] = matrix[p[0]][p[1]] + 1;
115+
visited[tempRow][tempCol] = true;
116+
queue.add(new int[]{tempRow, tempCol});
117+
}
118+
}
119+
}
120+
return matrix;
121+
}
122+
}
123+
```
124+
125+
* Method 3: DP
126+
```Java
127+
class Solution {
128+
public int[][] updateMatrix(int[][] matrix) {
129+
int height = matrix.length, width = matrix[0].length;
130+
int[][] result = new int[height][width];
131+
for(int i = 0; i < height; i++){
132+
for(int j = 0; j < width; j++){
133+
if(matrix[i][j] != 0){
134+
result[i][j] = 10000;
135+
if(i > 0) result[i][j] = Math.min(result[i][j], result[i - 1][j] + 1);
136+
if(j > 0) result[i][j] = Math.min(result[i][j], result[i][j - 1] + 1);
137+
}
138+
}
139+
}
140+
for(int i = height - 1; i >= 0; i--){
141+
for(int j = width - 1; j >= 0; j--){
142+
if(i < height - 1) result[i][j] = Math.min(result[i][j], result[i + 1][j] + 1);
143+
if(j < width - 1) result[i][j] = Math.min(result[i][j], result[i][j + 1] + 1);
144+
}
145+
}
146+
return result;
147+
}
148+
}
149+
```

‎leetcode/752. Open the Lock.md

Lines changed: 137 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,137 @@
1+
## 752. Open the Lock
2+
3+
### Qustion
4+
You have a lock in front of you with 4 circular wheels. Each wheel has 10 slots: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'. The wheels can rotate freely and wrap around: for example we can turn '9' to be '0', or '0' to be '9'. Each move consists of turning one wheel one slot.
5+
The lock initially starts at '0000', a string representing the state of the 4 wheels.
6+
You are given a list of deadends dead ends, meaning if the lock displays any of these codes, the wheels of the lock will stop turning and you will be unable to open it.
7+
Given a target representing the value of the wheels that will unlock the lock, return the minimum total number of turns required to open the lock, or -1 if it is impossible.
8+
9+
```
10+
Example 1:
11+
12+
Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202"
13+
Output: 6
14+
Explanation:
15+
A sequence of valid moves would be "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202".
16+
Note that a sequence like "0000" -> "0001" -> "0002" -> "0102" -> "0202" would be invalid,
17+
because the wheels of the lock become stuck after the display becomes the dead end "0102".
18+
19+
Example 2:
20+
21+
Input: deadends = ["8888"], target = "0009"
22+
Output: 1
23+
Explanation:
24+
We can turn the last wheel in reverse to move from "0000" -> "0009".
25+
26+
Example 3:
27+
28+
Input: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
29+
Output: -1
30+
Explanation:
31+
We can't reach the target without getting stuck.
32+
33+
Example 4:
34+
35+
Input: deadends = ["0000"], target = "8888"
36+
Output: -1
37+
```
38+
39+
Note:
40+
* The length of deadends will be in the range [1, 500].
41+
* target will not be in the list deadends.
42+
* Every string in deadends and the string target will be a string of 4 digits from the 10,000 possibilities '0000' to '9999'.
43+
44+
### Solution:
45+
* Method 1: bfs AC 73ms
46+
```Java
47+
class Solution {
48+
public int openLock(String[] deadends, String target) {
49+
HashSet<String> set = new HashSet<>();
50+
for(String s : deadends) set.add(s);
51+
if(set.contains(target) || set.contains("0000")) return -1;
52+
LinkedList<String> queue = new LinkedList<>();
53+
queue.add("0000");
54+
int len = target.length(), step = -1;
55+
Set<String> visited = new HashSet<>();
56+
while(!queue.isEmpty()){
57+
++step;
58+
int size = queue.size();
59+
for(int i = 0; i < size; i++){
60+
String cur = queue.poll();
61+
if(cur.equals(target)) return step;
62+
char[] arr = cur.toCharArray();
63+
for(int l = 0; l < len; l++){
64+
String next = null;
65+
// 1. Add 1
66+
arr[l] = arr[l] == '9' ? '0': (char)(arr[l] + 1);
67+
next = new String(arr);
68+
if(!set.contains(next) && !visited.contains(next)){
69+
queue.add(next);
70+
visited.add(next);
71+
}
72+
// 2. Deduct 1
73+
arr[l] = cur.charAt(l) == '0' ? '9': (char)(cur.charAt(l) - 1);
74+
next = new String(arr);
75+
if(!set.contains(next) && !visited.contains(next)){
76+
queue.add(next);
77+
visited.add(next);
78+
}
79+
arr[l] = cur.charAt(l);
80+
}
81+
}
82+
}
83+
return -1;
84+
}
85+
}
86+
```
87+
88+
* Method 2: Bi-directional bfs
89+
```Java
90+
class Solution {
91+
public int openLock(String[] deadends, String target) {
92+
Set<String> set = new HashSet<>();
93+
for(String s : deadends) set.add(s);
94+
if(set.contains(target) || set.contains("0000")) return -1;
95+
int len = 4, step = -1;
96+
Set<String> head = new HashSet<>(); head.add("0000");
97+
Set<String> tail = new HashSet<>(); tail.add(target);
98+
Set<String> visited = new HashSet<>();
99+
boolean found = false;
100+
while(!head.isEmpty() && !tail.isEmpty()){
101+
++step;
102+
Set<String> temp = null;
103+
if(head.size() > tail.size()){
104+
temp = head;
105+
head = tail;
106+
tail = temp;
107+
}
108+
Set<String> next = new HashSet<>();
109+
for(String cur : head){
110+
char[] arr = cur.toCharArray();
111+
for(int l = 0; l < 4; l++){
112+
String nextString = null;
113+
//Add 1
114+
arr[l] = arr[l] == '9' ? '0': (char)(arr[l] + 1);
115+
nextString = new String(arr);
116+
if(tail.contains(nextString)) return step + 1;
117+
if(!set.contains(nextString) && !visited.contains(nextString)){
118+
next.add(nextString);
119+
visited.add(nextString);
120+
}
121+
// Deduct 1
122+
arr[l] = cur.charAt(l) == '0' ? '9': (char)(cur.charAt(l) - 1);
123+
nextString = new String(arr);
124+
if(tail.contains(nextString)) return step + 1;
125+
if(!set.contains(nextString) && !visited.contains(nextString)){
126+
next.add(nextString);
127+
visited.add(nextString);
128+
}
129+
arr[l] = cur.charAt(l);
130+
}
131+
}
132+
head = next;
133+
}
134+
return -1;
135+
}
136+
}
137+
```

‎leetcode/943. Find the Shortest Superstring.md

Lines changed: 6 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -74,12 +74,12 @@ Note:
7474
for(int i = 0; i < A.length; i++){
7575
if((visited & (1 << i)) > 0) continue;
7676
path.add(i);
77-
dfs(A,
78-
cost,
79-
index + 1,
80-
index == 0 ? A[i].length(): temp + cost[path.get(index - 1)][i],
81-
path,
82-
res,
77+
dfs(A,
78+
cost,
79+
index + 1,
80+
index == 0 ? A[i].length(): temp + cost[path.get(index - 1)][i],
81+
path,
82+
res,
8383
(visited | (1 << i)));
8484
path.remove(index);
8585
}

‎leetcode/996. Number of Squareful Arrays.md

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -10,15 +10,15 @@ Example 1:
1010
1111
Input: [1,17,8]
1212
Output: 2
13-
Explanation:
13+
Explanation:
1414
[1,8,17] and [17,8,1] are the valid permutations.
1515
1616
Example 2:
1717
1818
Input: [2,2,2]
1919
Output: 1
2020
```
21-
21+
2222
Note:
2323
* 1 <= A.length <= 12
2424
* 0 <= A[i] <= 1e9

0 commit comments

Comments
 (0)