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
| class Solution {
private final int[][] DIRECTIONS = new int[][] { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
public boolean containsCycle(char[][] grid) {
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] >= 97 && hasCycle(grid, i, j, -1, -1)) {
return true;
}
}
}
return false;
}
private boolean hasCycle(char[][] grid, int row, int col, int prevRow, int prevCol) {
char currChar = grid[row][col];
grid[row][col] -= 32;
for (int[] direction : DIRECTIONS) {
int newRow = row + direction[0];
int newCol = col + direction[1];
if (!isOutBound(grid, newRow, newCol) && (newRow != prevRow || newCol != prevCol) &&
Character.toLowerCase(grid[newRow][newCol]) == currChar) {
if (grid[newRow][newCol] != currChar) {
return true;
} else if (hasCycle(grid, newRow, newCol, row, col)) {
return true;
}
}
}
return false;
}
private boolean isOutBound(char[][] grid, int row, int col) {
return row < 0 || row >= grid.length || col < 0 || col >= grid[0].length;
}
}
|
真杂种操了. 第21行第二个扩起来的两个条件, 判断不能是走回头路那个, 那是or不能写成and. 写成and是既不能有相同的row也不能有相同的col. 这肯定不对, 二者一个不一样即可.
我们visit过的地方, 如果走不通, 那这个地方一定不在cycle中. 可以用反证法来证明. 假设它在cycle中, 那么一定会有路走, 要么是走之前没走过的要么就是走到了之前走过的地方, 形成cycle. 因此只要是back回来的, 标记过的走过的点都不恢复. 之后遍历的时候, 如果走过之前走过的点, 这说明遇到了cycle. 问题是a标记好的走过的点如果我们在找b的cycle的时候不混淆呢? 也就是b走过的点也要标记, 如何区分a做过的点和b走过的点呢? 我想的是转大写. a走过的点统一变成‘A’, b走过的点统一变成‘B’. 这样就不会混淆了, 否则我们会误认为a标记的点是b标记的而错误地以为形成了cycle.
记得大写从65开始, 小写从97开始.
时间复杂度: O(m * n)
空间复杂度: O(m * n)
