美团春招实习笔试，懵逼了！

输入：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出：1

输入：grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出：3

// 岛屿数量（LeetCode 200）（并查集解法）：https://leetcode.cn/problems/number-of-islands/
class Solution {
    private int rows;

    private int cols;

    public int numIslands(char[][] grid) {

        rows = grid.length;

        cols = grid[0].length;

        // 水格的数量
        int spaces = 0;

        UnionFind unionFind = new UnionFind(rows * cols);

        // 沿着每个网格的右方、下方去查找
        int[][] directions = {{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 {
                    
                    // 沿着这个陆地的右方、下方这两个方向去查找
                    for (int[] direction : directions) {
                        
                        // 新网格的 x 坐标
                        int newX = i + direction[0];

                        // 新网格的 y 坐标
                        int newY = j + direction[1];

                        // 如果新网格的坐标位于矩阵内
                        // 并且是陆地
                        if (newX < rows && newY < cols && grid[newX][newY] == '1') {
                            // 那么就把这两个网格连接起来
                            unionFind.union(getIndex(i, j), getIndex(newX, newY));
                        }
                    }
                }
            }
        }
        return unionFind.getCount() - spaces;

    }

    // 把这些二维网格进行编号
    // 比如第 0 行第 0 列网格的编号是 0 
    // 比如第 0 行第 1 列网格的编号是 1
    // 比如第 1 行第 1 列网格的编号是 5（一列有 5 个元素）  
    private int getIndex(int i, int j) {
        return i * cols + j;
    }
}

// 并查集
class UnionFind {

    int[] roots;

    int count;

    public UnionFind(int n) {
        // 使用一维数组用来记录每个网格的出发位置
        roots = new int[n];
        for (int i = 0; i < n  ; i++) {
            // 默认每个网格的出发位置是自己本身
            roots[i] = i;
        }
        // 所以一开始有 n 个岛屿
        count = n ;
    }
    
    // 寻找当前网格的出发位置
    public int find(int i){
        
        if( i == roots[i]) return i ;

        roots[i] = find(roots[i]);

        return roots[i];

    }

    // 连通操作，把陆地连接起来
    public void union(int p, int q) {
        // 寻找陆地 p 的出发位置
        int pRoot = find(p);

        // 寻找陆地 q 的出发位置
        int qRoot = find(q);

        // 如果两者的出发位置不同
        // 那么需要采取操作把 p 和 q 所在的两堆网格合到一起
        if (pRoot != qRoot) {
            // 也就是把其中一个的最上面的出发位置挂过来就行
            roots[pRoot] = qRoot;
            // 与此同时，两堆陆地变成了一堆陆地
            count--;
        }
    }

    // 获取当前区间的所有连通量
    public int getCount() {

        // 也就是有多少陆地网格 + 水网格
        return count;
    }

}