岛屿数量

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。此外，你可以假设该网格的四条边均被水包围。

岛屿数量

思路 暴力递归（最优解） #

public int numIslands1(char[][] grid) {
  int islands = 0;
  for (int i = 0; i < grid.length; i++) {
    for (int j = 0; j < grid[0].length; j++) {
      if (grid[i][j] == '1') {
        islands++;
        infect(grid, i, j); // 感染
      }
    }
  }
  return islands;
}

// 从(i,j)这个位置出发，把所有连成一片的'1'字符，变成0（acsii）
private void infect(char[][] grid, int i, int j) {
  if (i < 0 || i == grid.length || j < 0 || j == grid[0].length || grid[i][j] != '1') {
    return;
  }
  grid[i][j] = 0;
  infect(grid, i - 1, j);
  infect(grid, i + 1, j);
  infect(grid, i, j - 1);
  infect(grid, i, j + 1);
}

并查集（HashMap）实现 #

缺点：HashMap 的常数时间较大

public static int numIslands2(char[][] board) {
  int row = board.length;
  int col = board[0].length;
  UnionFind2 uf = new UnionFind2(board);
  for (int j = 1; j < col; j++) {
    if (board[0][j - 1] == '1' && board[0][j] == '1') {
      uf.union(0, j - 1, 0, j);
    }
  }
  for (int i = 1; i < row; i++) {
    if (board[i - 1][0] == '1' && board[i][0] == '1') {
      uf.union(i - 1, 0, i, 0);
    }
  }
  for (int i = 1; i < row; i++) {
    for (int j = 1; j < col; j++) {
      if (board[i][j] == '1') {
        if (board[i][j - 1] == '1') {
          uf.union(i, j - 1, i, j);
        }
        if (board[i - 1][j] == '1') {
          uf.union(i - 1, j, i, j);
        }
      }
    }
  }
  return uf.sets();
}

并查集（Array）实现 #

优化 HashMap 的常数时间

public static int numIslands3(char[][] grid) {
  int row = grid.length;
  int col = grid[0].length;
  UnionFind2 uf = new UnionFind2(grid);
  for (int j = 1; j < col; j++) {
    if (grid[0][j - 1] == '1' && grid[0][j] == '1') {
      uf.union(0, j - 1, 0, j);
    }
  }
  for (int i = 1; i < row; i++) {
    if (grid[i - 1][0] == '1' && grid[i][0] == '1') {
      uf.union(i - 1, 0, i, 0);
    }
  }
  for (int i = 1; i < row; i++) {
    for (int j = 1; j < col; j++) {
      if (grid[i][j] == '1') {
        if (grid[i][j - 1] == '1') {
          uf.union(i, j - 1, i, j);
        }
        if (grid[i - 1][j] == '1') {
          uf.union(i - 1, j, i, j);
        }
      }
    }
  }
  return uf.sets();
}