LeetCode 200 - Number of Islands

作者 QIFAN 日期 2017-01-28
LeetCode 200 - Number of Islands

原题链接: 200. Number of Islands


题干

给定一个二维矩阵,其中只包括 0 和 1 ,1 代表土地,0 代表海水,返回独立岛屿的数量。

思路

DFS

思路是:遍历矩阵,当某个点的值为 1 ,将这个点的值改为 0 ,并对其周围的四个点进行 DFS ,结束后岛屿数量加一,这样整个 DFS 结束时,相邻的一片 1 都变成了 0 。

代码:

public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
int M = grid.length;
int N = grid[0].length;
int count = 0;
for (int row = 0; row < M; row++) {
for (int col = 0; col < N; col++) {
if (grid[row][col] == '1') {
DFS(row, col, grid);
count++;
}
}
}
return count;
}
private void DFS(int row, int col, char[][] grid) {
if (row < 0 || row >= grid.length || col < 0 || col >= grid[0].length || grid[row][col] != '1') {
return;
}
grid[row][col] = '0';
DFS(row - 1, col, grid);
DFS(row + 1, col, grid);
DFS(row, col - 1, grid);
DFS(row, col + 1, grid);
}

Union Find

Union Find 解法,具体介绍看这里:Union Find

思路是:

  • 新建一个数组,用来记录每个格子所在属的岛屿。一开始每个格子都是自成岛屿。
  • 从上到下一行行检查,对每一个是 1 的格子,检查它左边与上边格子,如果有 1 则与该岛屿相连;对 0 格子,将岛屿编号设为 -1 。
  • 最后遍历数组,岛屿编号等于自己 index 的格子个数就是岛屿的个数。

代码:

public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
int M = grid.length;
int N = grid[0].length;
int[] islands = new int[M * N];
// 初始化数值为其 index
for (int i = 0; i < islands.length; i++) {
islands[i] = i;
}
for (int row = 0; row < M; row++) {
for (int col = 0; col < N; col++) {
int index = row * N + col;
if (grid[row][col] == '0') {
islands[index] = -1;
} else {
// 将格子与上方岛屿相连
if (row > 0 && grid[row - 1][col] == '1') {
islands[root(index, islands)] = root(index - N, islands);
}
// 将格子与左方岛屿相连
if (col > 0 && grid[row][col - 1] == '1') {
islands[root(index, islands)] = root(index - 1, islands);
}
}
}
}
int count = 0;
for (int i = 0; i < islands.length; i++) {
if (islands[i] == i) {
count++;
}
}
return count;
}
private int root(int index, int[] islands) {
while (index != islands[index]) {
index = islands[index];
}
return index;
}