200. 岛屿数量 - 力扣（LeetCode）
一、题目
给你一个由?'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
示例 2：
输入：grid = [
? ["1","1","0","0","0"],
? ["1","1","0","0","0"],
? ["0","0","1","0","0"],
? ["0","0","0","1","1"]
]
输出：3
提示：
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 300
- grid[i][j] 的值为 '0' 或 '1'
二、代码
class Solution {
// 并查集
public static class UnionFind {
private int[] parents;
private int[] size;
private int[] stack;
private int row;
private int col;
private int set;
// 初始化并查集
public UnionFind(char[][] grid) {
row = grid.length;
col = grid[0].length;
set = 0;
parents = new int[row * col];
size = new int[row * col];
stack = new int[row * col];
// 将所有为'1'的元素做作为一个独立集合加入并查集
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[i].length; j++) {
if (grid[i][j] == '1') {
// 将二维下标转换为一维下标存入并查集中，并用这个下标唯一标识元素
int index = toIndex(i, j);
parents[index] = index;
size[index] = 1;
set++;
}
}
}
}
// 二位下标转换为一维下标
public int toIndex(int r, int c) {
return r * col + c;
}
// 找到代表节点
public int findFather(int i) {
int cur = i;
int p = 0;
while (parents[cur] != cur) {
stack[p++]= cur;
cur = parents[cur];
}
// 路径压缩
while (p > 0) {
parents[stack[--p]] = cur;
}
return cur;
}
// 合并操作
public void union(int r1, int c1, int r2, int c2) {
// 先将二维下标转换为一维下标
int index1 = toIndex(r1, c1);
int index2 = toIndex(r2, c2);
// 找到两个要合并样本的代表节点
int father1 = findFather(index1);
int father2 = findFather(index2);
// 如果两个代表节点不一样，说明两个样本目前不在一个集合内，去要进行合并操作
if (father1 != father2) {
// 小集合并入大集合，这样也能压缩查找代表节点的路径
int big = size[father1] > size[father2] ? father1 : father2;
int small = big == father1 ? father2 : father1;
parents[small] = big;
size[big] += size[small];
// 将并查集中独立集合书减1
set--;
}
}
// 返回并查集中独立集合数
public int set() {
return set;
}
}
public static int numIslands(char[][] grid) {
int rol = grid.length;
int col = grid[0].length;
// 构造并查集
UnionFind uf = new UnionFind(grid);
// 下面遍历所有节点，对符合条件的节点进行合并，合并原则就是每一个节点和自己相邻的左边和上面的节点做判断，如果都是'1'，则将两者进行合并
// 先单独合并第一列和第一行的元素，这样就不用考虑边界了
for (int i = 1; i < rol; i++) {
if (grid[i][0] == '1') {
if (grid[i - 1][0] == '1') {
uf.union(i, 0, i - 1, 0);
}
}
}
for (int j = 1; j < col; j++) {
if (grid[0][j] == '1') {
if (grid[0][j - 1] == '1') {
uf.union(0, j, 0, j - 1);
}
}
}
// 合并剩下的元素
for (int i = 1; i < rol; i++) {
for (int j = 1; j < col; j++) {
if (grid[i][j] == '1') {
if (grid[i - 1][j] == '1') {
uf.union(i, j, i - 1, j);
}
if (grid[i][j - 1] == '1') {
uf.union(i, j, i, j - 1);
}
}
}
}
// 合并完成后并查集中还存在的独立集合数，就是岛屿数
return uf.set();
}
}
三、解题思路
这道题的题意就是找到岛屿的数量，很明显就是一个利用并查集的合并操作，将所有的元素都合并完，再去还剩下多少个独立集合的问题。每一个岛屿就是一个独立的集合。
这里有一个注意点就是需要区分不同的样本，显然要进行合并的样本的值都是字符’1‘，我们无法通过值去区分，并且char在Java还是值传递，也无法使用地址区分。所以要么我们通过在外面包一层包装类然后通过地址区分，要么我们将二维下标转换为唯一的一维下标，然后通过这个唯一的一维下标去区分。我们使用的是后者、
|