Leetcode - Number of Islands

[分析]
BFS & DFS法详见实现。
这里阐述下union-find思路，思路很直接，我们需要把相连在一起的1union起来，最后数下union了多少个集合1。输入时一个m*n矩阵，union-find相应地需要一个二维数组保存信息，采用按秩求并方法，初始时每个1元素的秩为-1,0元素不参与union，记为0。扫描数组，对于(i,j)元素，查看其是否需要同右边和下边相邻元素合并，其上边和左边不需要，因为按这种扫描顺序已经查看过。一个相邻的1集合合并完，只有根节点的秩为负数，而其余节点均指向相应根节点的下标为正数，因此扫描完整个集合，通过检查秩数组中负数的个数即可知道grid中的岛屿数。特别注意，在union时若两个元素根相同说明已经被union过，不能再执行union逻辑否则会导致该集合的根消失而Wrong Answer。

--第二版union find，一维数组存储，更清晰，使用count计数岛屿数，初始时每个1所在位置为一个岛屿，伴随union过程，相连的1代表的岛屿进行合并，每一次成功合并，岛屿数减一。实现如Method 4所示。当然此题用BFS或者DFS代码比较简洁, DFS的隐患是可能堆栈溢出。

public int numIslands1(char[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0)
            return 0;
        initUnionFind(grid);
        int rows = grid.length;
        int cols = grid[0].length;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == '1') {
                    for (int k = 0; k < 4; k++) {
                        int iNeigh = i + deltaY[k];
                        int jNeigh = j + deltaX[k];
                        if (iNeigh >= 0 && iNeigh < rows && jNeigh >= 0 && jNeigh < cols && grid[iNeigh][jNeigh] == '1') {
                            union(i * cols + j, iNeigh * cols + jNeigh);
                        }
                    }
                }
            }
        }
        return count;
    }
    int[] s;
    int[] rank;
    int count = 0;
    int[] deltaX = {0, 0, 1, -1};
    int[] deltaY = {1, -1, 0, 0};
    private void union(int p, int q) {
        int pRoot = find(p), qRoot = find(q);
        if (pRoot == qRoot) return;
        if (s[pRoot] > s[qRoot]) {
            s[pRoot] = qRoot;
        } else {
            if (s[pRoot] == s[qRoot])
                s[pRoot]--;
            s[qRoot] = pRoot;
        }
        count--;
    }
    private int find1(int p) {
        if (s[p] == p)
            return p;
        else
            return s[p] = find(s[p]);
    }
    private void union1(int p, int q) {
        int pRoot = find(p), qRoot = find(q);
        if (pRoot == qRoot) return;
        if (rank[pRoot] < rank[qRoot]) {
            s[pRoot] = qRoot;
        } else {
            if (rank[pRoot] == rank[qRoot])
                rank[pRoot]++;
            s[qRoot] = s[pRoot];
        }
        count--;
    }

// Method 3:Union-Find
public class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0)
            return 0;
        initUnionFind(grid);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '0') continue;
                if (j + 1 < n && grid[i][j + 1] == '1')
                    union(i, j, i, j + 1);
                if (i + 1 < m && grid[i + 1][j] == '1')
                    union(i, j, i + 1, j);
            }
        }
        int count = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (s[i][j] < 0)
                    count++;
            }
        }
        return count;
    }
    int[][] s;
    int m, n;
    public void initUnionFind(char[][] grid) {
        m = grid.length;
        n = grid[0].length;
        s = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1')
                    s[i][j] = -1;
            }
        }
    }
    public int find(int i, int j) {
        if (s[i][j] < 0) {
            return i * n + j;
        } else {
            return s[i][j] = find(s[i][j] / n, s[i][j] % n);
        }
    }
    public void union(int i1, int j1, int i2, int j2) {
        int root1 = find(i1, j1), root2 = find(i2, j2);
        if (root1 == root2) return; // without this, fail @["111","111","111"]
        int iRoot1 = root1 / n, jRoot1 = root1 % n;
        int iRoot2 = root2 / n, jRoot2 = root2 % n;
        if (s[iRoot1][jRoot1] < s[iRoot2][jRoot2]) {
            s[iRoot2][jRoot2] = iRoot1 * n + jRoot1;
        } else {
            if (s[iRoot1][jRoot1] == s[iRoot2][jRoot2])
                s[iRoot2][jRoot2]--;
            s[iRoot1][jRoot1] = iRoot2 * n + jRoot2;
        }
    }
}

// Method 2: DFS
public class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0)
            return 0;
        int m = grid.length, n = grid[0].length;
        int count = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    count++;
                    dfs(i, j, grid);
                }
            }
        }
        return count;
    }
    public void dfs(int i, int j, char[][] grid) {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == '0')
            return;
        grid[i][j] = '0';
        dfs(i - 1, j, grid);
        dfs(i + 1, j, grid);
        dfs(i, j - 1, grid);
        dfs(i, j + 1, grid);
    }
}

// Method 1:BFS
public class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0)
            return 0;
        int rows = grid.length, cols = grid[0].length;
        int num = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == '1') {
                    bfs(i, j, grid);
                    num++;
                }
            }
        }
        return num;
    }
    private void bfs(int i, int j, char[][] grid) {
        grid[i][j] = '2';
        LinkedList<Integer> queue = new LinkedList<Integer>();
        int cols = grid[0].length;
        queue.offer(i * cols + j);
        while (!queue.isEmpty()) {
            int idx = queue.poll();
            int r = idx / cols;
            int c = idx % cols;
            visit(r + 1, c, grid, queue);
            visit(r - 1, c, grid, queue);
            visit(r, c + 1, grid, queue);
            visit(r, c - 1, grid, queue);
        }
    }
    private void visit(int i, int j, char[][] grid, LinkedList<Integer> queue) {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] != '1')
            return;
        grid[i][j] = '2';
        queue.offer(i * grid[0].length + j);
    }
}