给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。
示例 1:
输入:
11110
11010
11000
00000输出: 1
示例 2:输入:
11000
11000
00100
00011输出: 3
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-islands
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
使用并查集
class Solution {
/**
* 使用并查集
*
* @param grid
* @return
*/
public int numIslands(char[][] grid) {
if (grid.length == 0 || grid[0].length == 0) {
return 0;
}
int m = grid.length;
int n = grid[0].length;
// 初始化并查集对象
UnionFind uf = new UnionFind(m * n);
// 遍历所有的岛屿，合并岛屿
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '0') {
// 岛屿数量减1
uf.decCount();
continue;
}
// 与左边的岛屿合并
if (i > 0 && grid[i - 1][j] == '1') {
uf.union((i - 1) * n + j, i * n + j);
}
// 与上面的岛屿合并
if (j > 0 && grid[i][j - 1] == '1') {
uf.union(i * n + (j - 1), i * n + j);
}
}
}
return uf.getCount();
}
class UnionFind {
int[] roots; // 存储并查集
int count = 0; // 岛屿个数
public UnionFind(int n) {
roots = new int[n];
// 初始化并查集
for (int i = 0; i < n; i++) {
// 并查集节点自己指向自己
roots[i] = i;
count ++;
}
}
/**
* 获取root
*
* @param p
* @return
*/
public int findRoot(int p) {
// 获取root
int root = p;
while (root != roots[root]) {
root = roots[root];
}
// 缩短路径，将路径上的所有节点的root全部赋为找到root
int i = p;
while (i != roots[i]) {
int tmp = roots[i];
roots[i] = root;
i = tmp;
}
return root;
}
/**
* 合并
*
* @param p1
* @param p2
*/
public void union(int p1, int p2) {
int root1 = findRoot(p1);
int root2 = findRoot(p2);
if (root1 != root2) {
roots[root2] = root1;
// 两个岛屿合并，计数减1
decCount();
}
}
public void decCount() {
count --;
}
public int getCount() {
return count;
}
}
public static void main(String[] args) {
char[][] grids = {{'1', '1', '1', '1', '0'}, {'1', '1', '0', '1', '0'}, {'1', '1', '0', '0', '0'}, {'0', '0', '0', '0', '0'}};
int result = new Solution().numIslands(grids);
System.out.println(result);
}
}
运行效率
DFS深度优先搜索
class Solution {
private char[][] grid;
private boolean[][] visited; // 已经浏览过的岛屿
private int[][] direction = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
private int row; // 行
private int column; // 列
/**
* DFS
*
* @param grid
* @return
*/
public int numIslands(char[][] grid) {
if (grid.length == 0 || grid[0].length == 0) {
return 0;
}
this.grid = grid;
this.row = grid.length;
this.column = grid[0].length;
this.visited = new boolean[row][column];
int count = 0;
for (int i = 0; i < row; i++) {
for (int j = 0; j < column; j++) {
if (visited[i][j] || grid[i][j] == '0') {
continue;
}
visit(i, j);
count ++;
}
}
return count;
}
/**
* DFS深度优先搜索，找到一个就延四个方向深入搜索
*
* @param x
* @param y
*/
private void visit(int x, int y) {
visited[x][y] = true;
for (int i = 0; i < direction.length; i++) {
int dirX = direction[i][0];
int dirY = direction[i][1];
if (x + dirX < 0 || x + dirX >= row || y + dirY < 0 || y + dirY >= column
|| visited[x + dirX][y + dirY] || grid[x + dirX][y + dirY] == '0') {
continue;
}
visit(x + dirX, y + dirY);
}
}
}
运行效率
BFS广度优先搜索
class Solution {
private char[][] grid;
private boolean[][] visited;
private int row;
private int column;
// 存储坐标(x, y) 的计算值，需要能够通过值得到 (x, y)
// value = x * row * column + y
// y = value % (row * column)
// x = (value - y) / (row * column)
private Queue<Integer> queue;
private int[][] direction = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
private int count = 0;
/**
* BFS广度优先搜索
*
* @param grid
* @return
*/
public int numIslands(char[][] grid) {
if (grid.length == 0 || grid[0].length == 0) {
return 0;
}
this.grid = grid;
this.row = grid.length;
this.column = grid[0].length;
this.visited = new boolean[row][column];
this.queue = new LinkedList<>();
for (int i = 0; i < row; i++) {
for (int j = 0; j < column; j++) {
if (!visited[i][j] && grid[i][j] == '1') {
visited[i][j] = true;
queue.add(i * (row * column) + j);
visit();
count++;
}
}
}
return count;
}
/**
* BFS广度优先搜索
*/
private void visit() {
while (!queue.isEmpty()) {
int position = queue.remove();
int y = position % (row * column);
int x = (position - y) / (row * column);
for (int[] dir : direction) {
int dirX = dir[0];
int dirY = dir[1];
if (validPosition(x + dirX, y + dirY)
&& !visited[x + dirX][y + dirY] && grid[x + dirX][y + dirY] == '1') {
visited[x + dirX][y + dirY] = true;
queue.add((x + dirX) * row * column + (y + dirY));
}
}
}
}
/**
* 校验坐标是否合法
*
* @param x
* @param y
* @return
*/
private boolean validPosition(int x, int y) {
return x >= 0 && x < row && y >= 0 && y < column;
}
public static void main(String[] args) {
char[][] grid = {{'1', '1', '1', '1', '0'}, {'1', '1', '0', '1', '0'}, {'1', '1', '0', '0', '0'}, {'0', '0', '0', '0', '0'}};
int result = new Solution().numIslands(grid);
System.out.println(result);
}
}
运行效率
网友评论