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 int numDistinctIslands(int[][] grid) {
int m = grid.length, n = grid[0].length;
Set<String> paths = new HashSet<>();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
StringBuilder sb = new StringBuilder();
getPath(grid, i, j, sb);
paths.add(sb.toString());
}
}
}
return paths.size();
}
private void getPath(int[][] grid, int row, int col, StringBuilder sb) {
grid[row][col] = 0;
for (int i = 0; i < DIRECTIONS.length; i++) {
int newRow = row + DIRECTIONS[i][0];
int newCol = col + DIRECTIONS[i][1];
if (!isOutOfBound(grid.length, grid[0].length, newRow, newCol) && grid[newRow][newCol] == 1) {
sb.append(i);
getPath(grid, newRow, newCol, sb);
}
}
sb.append('0');
}
private boolean isOutOfBound(int m, int n, int row, int col) {
return row < 0 || row >= m || col < 0 || col >= n;
}
}
|
很直接的想法就是从一个1开始, dfs一个island, 如果我们走的方向都一模一样, 这两个岛也就一样. 但需要注意的是, 我们返回上一层的时候也要记录. 因为如果只记录递归往下走不记录往上走, 那么不同的岛最后输出来的东西可能也是一样的.
比如:
[1 1 0
0 1 1
0 0 0
1 1 1
0 1 0]
这两个岛如果我们dfs在return前不加个标记, 只是深入的时候标记, 那么它们产生的string是一样的. 我们用0表示上, 1表示下, 2表示左, 3表示右. 第一个岛就是3 1 3. 第二个岛也是3 1 3. 这是因为在第二个位置, 对于第一个岛, 它上不能走那先走下, 于是有个1. 然后到了新位置后上下左都不行于是去了右加了个3. 那么我们如果不知道就会想, 最后这个3是在哪里往右的? 是往下后往右的? 还是往下后哪儿也去不了又回到上一个位置往右的? 于是我们要在返回时也加上标记.
时间复杂度: O(m * n)
空间复杂度: O(1) 因为我们是直接在grid上做标记, 到一个地方后, 把1变为0.
