给你一个由 '1'(陆地)和 '0'(水)组成的的二维网格,请你计算网格中岛屿的数量。
岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外,你可以假设该网格的四条边均被水包围。
示例 1:
输入:grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
输出:1
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/number-of-islands
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解析
很明显套公式就好了。
解法二我们练习一下并查集的解法。
解法一
class Solution {
public int numIslands(char[][] grid) {
int res = 0;
for (int r = 0; r < grid.length; r++) {
for (int c = 0; c < grid[0].length; c++) {
if (grid[r][c] == '1') {
dfs(grid, r, c);
res++;
}
}
}
return res;
}
void dfs(char[][] grid, int r, int c) {
// 函数因为「坐标 (r, c) 超出网格范围」
// 函数因为「当前格子是海洋格子」或者【被访问过】
if (!inArea(grid, r, c) || grid[r][c] != '1') {
return;
}
grid[r][c] = '2';
dfs(grid, r - 1, c);
dfs(grid, r + 1, c);
dfs(grid, r, c - 1);
dfs(grid, r, c + 1);
}
// 判断坐标 (r, c) 是否在网格中
boolean inArea(char[][] grid, int r, int c) {
return 0 <= r && r < grid.length
&& 0 <= c && c < grid[0].length;
}
}
解法二
并查集,我们对于并查集的count设置为1的个数,每一次遍历到1就进行将他的上下左右都进行union
注意还有另外一种并查集的写法,就是将二维数组的x*y 作为总的连通分量,最后用uf.count()-space空格数就得到了答案。
class Solution {
class UnionFind {
int count;
int[] parent;
int[] rank;
public UnionFind(char[][] grid) {
count = 0;
int m = grid.length;
int n = grid[0].length;
parent = new int[m * n];
rank = new int[m * n];
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == '1') {
parent[i * n + j] = i * n + j;
++count;
}
rank[i * n + j] = 0;
}
}
}
public int find(int i) {
if (parent[i] != i) parent[i] = find(parent[i]);
return parent[i];
}
public void union(int x, int y) {
int rootx = find(x);
int rooty = find(y);
if (rootx != rooty) {
if (rank[rootx] > rank[rooty]) {
parent[rooty] = rootx;
} else if (rank[rootx] < rank[rooty]) {
parent[rootx] = rooty;
} else {
parent[rooty] = rootx;
rank[rootx] += 1;
}
--count;
}
}
public int getCount() {
return count;
}
}
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
int nr = grid.length;
int nc = grid[0].length;
int num_islands = 0;
UnionFind uf = new UnionFind(grid);
for (int r = 0; r < nr; ++r) {
for (int c = 0; c < nc; ++c) {
if (grid[r][c] == '1') {
grid[r][c] = '2';
if (r - 1 >= 0 && grid[r-1][c] == '1') {
uf.union(r * nc + c, (r-1) * nc + c);
}
if (r + 1 < nr && grid[r+1][c] == '1') {
uf.union(r * nc + c, (r+1) * nc + c);
}
if (c - 1 >= 0 && grid[r][c-1] == '1') {
uf.union(r * nc + c, r * nc + c - 1);
}
if (c + 1 < nc && grid[r][c+1] == '1') {
uf.union(r * nc + c, r * nc + c + 1);
}
}
}
}
return uf.getCount();
}
}
//另外一种写法
public class Solution {
private int rows;
private int cols;
public int numIslands(char[][] grid) {
rows = grid.length;
if (rows == 0) {
return 0;
}
cols = grid[0].length;
// 空地的数量
int spaces = 0;
UnionFind unionFind = new UnionFind(rows * cols);
int[][] directions = {{1, 0}, {0, 1},{-1, 0}, {0, -1}};
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == '0') {
spaces++;
} else {
// 此时 grid[i][j] == '1'
for (int[] direction : directions) {
int newX = i + direction[0];
int newY = j + direction[1];
// 先判断坐标合法,再检查右边一格和下边一格是否是陆地
if (newX >=0 && newY>=0 && newX < rows && newY < cols && grid[newX][newY] == '1') {
unionFind.union(getIndex(i, j), getIndex(newX, newY));
}
}
}
}
}
return unionFind.getCount() - spaces;
}
private int getIndex(int i, int j) {
return i * cols + j;
}
private class UnionFind {
/**
* 连通分量的个数
*/
private int count;
private int[] parent;
public int getCount() {
return count;
}
public UnionFind(int n) {
this.count = n;
parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
private int find(int x) {
while (x != parent[x]) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
public void union(int x, int y) {
int xRoot = find(x);
int yRoot = find(y);
if (xRoot == yRoot) {
return;
}
parent[xRoot] = yRoot;
count--;
}
}
}
注意:本文归作者所有,未经作者允许,不得转载