【LC總結(jié)】Union Find系列(Num of Islands I&II/Graph V

bergwhite 發(fā)布于2019-08-14 15:51 / 2392人閱讀

摘要：不得不說，對于這道題而言，是一種很木訥的模板。主函數(shù)按矩陣大小建立一個類進行后續(xù)操作一個結(jié)點用來連接邊角不可能被圍繞的一個函數(shù)對矩陣元素進行結(jié)點線性化。同理，，，在主函數(shù)中初始化后調(diào)用。

Surrounded Regions Problem

Given a 2D board containing "X" and "O" (the letter O), capture all regions surrounded by "X".

A region is captured by flipping all "O"s into "X"s in that surrounded region.

For example,

X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

Note

不得不說，對于這道題而言，Union Find是一種很木訥的模板。

主函數(shù)：按矩陣大小建立：

一個UnionFind類進行后續(xù)操作；

一個dummy結(jié)點用來連接邊角不可能被X圍繞的O；

一個node()函數(shù)對矩陣元素進行結(jié)點線性化。

操作：

遍歷所有結(jié)點，矩陣邊角的O與dummy相連，矩陣內(nèi)部的O與相鄰的O相連；

遍歷所有結(jié)點，與dummy相連的結(jié)點設(shè)置為O，其它所有結(jié)點設(shè)置為X。

UnionFind函數(shù)：建立：

全局變量parents；

初始化函數(shù)UnionFind(int size)；

查找parents函數(shù)find(int node)；

歸并函數(shù)union(int node1, int node2)；

測試兩結(jié)點是否相連函數(shù)isConnected(int node1, int node2)；

操作：

find(int node): 用while循環(huán)向上查找node的parent，注意先向上迭代parents[node]，再迭代node，否則會超時；

union(int node1, int node2): 找到兩個結(jié)點的parents，r1和r2，令parents[r1] = r2；

isConnected(int n1, int n2): 查看兩個結(jié)點的parents是否相等。

Solution

public class Solution {
    int row, col;
    public void solve(char[][] board) {
        if (board == null || board.length == 0) return;
        row = board.length;
        col = board[0].length;
        UnionFind uf = new UnionFind(row*col+1);
        int dummy = row*col;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (board[i][j] == "O") {
                    if (i == 0 || i == row-1 || j == 0 || j == col-1) uf.union(node(i, j), dummy);
                    else {
                        if (i > 0 && board[i-1][j] == "O") uf.union(node(i, j), node(i-1, j));
                        if (i > 0 && board[i+1][j] == "O") uf.union(node(i, j), node(i+1, j));
                        if (j > 0 && board[i][j-1] == "O") uf.union(node(i, j), node(i, j-1));
                        if (j > 0 && board[i][j+1] == "O") uf.union(node(i, j), node(i, j+1));
                    }
                }
            }
        }
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (uf.isConnected(node(i, j), dummy)) board[i][j] = "O";
                else board[i][j] = "X";
            }
        }
    }
    public int node(int i, int j) {
        return i*col+j;
    }
}

class UnionFind {
    int[] parents;
    public UnionFind(int n) {
        parents = new int[n];
        for (int i = 0; i < n; i++) parents[i] = i;
    }
    public void union(int n1, int n2) {
        int r1 = find(n1);
        int r2 = find(n2);
        if (r1 != r2) parents[r1] = r2;
    }
    public int find(int node) {
        if (parents[node] == node) return node;
        parents[node] = find(parents[node]);
        return parents[node];
    }    
    public boolean isConnected(int n1, int n2) {
        return find(n1) == find(n2);
    }
}

Graph Valid Tree Problem

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.

For example:

Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.

Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.

Note

同理，find，union，在主函數(shù)中初始化后調(diào)用。

Solution

public class Solution {
    int[] parents;
    public boolean validTree(int n, int[][] edges) {
        if (edges.length != n-1) return false;
        parents = new int[n];
        for (int i = 0; i < n; i++) parents[i] = i;
        for (int i = 0; i < n-1; i++) {
            if (find(edges[i][0]) == find(edges[i][1])) return false;
            union(edges[i][0], edges[i][1]);
        }
        return true;
    }
    public int find(int n) {
        if (parents[n] == n) return n;
        parents[n] = find(parents[n]);
        return parents[n];
    }
    public void union(int n1, int n2) {
        int r1 = find(n1);
        int r2 = find(n2);
        if (r1 != r2) parents[r1] = r2;
    }
}

Number of Islands Problem

Given a 2d grid map of "1"s (land) and "0"s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

Answer: 1

Example 2:

Answer: 3

Note Solution

public class Solution {

    class UnionFind {
        public int count;
        public int[] parents;
        public UnionFind(int m, int n, char[][] grid) {
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (grid[i][j] == "1") count++;
                }
            }
            parents = new int[m*n];
            for (int i = 0; i < m*n; i++) parents[i] = i;
        }
        public int find(int i) {
            if (i == parents[i]) return i;
            parents[i] = find(parents[i]);
            return parents[i];
        }
        public void union(int i, int j) {
            int pi = find(i);
            int pj = find(j);
            if (pi == pj) return;
            else parents[pi] = pj;
            count--;
        }
        public boolean isConnected(int i, int j) {
            return find(i) == find(j);
        }
    }
    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;
        UnionFind uf = new UnionFind(m, n, grid);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == "0") continue;
                int x = i*n+j;
                int y;
                if (i < m-1 && grid[i+1][j] == "1") {
                    y = x+n;
                    uf.union(x, y);
                }
                if (j < n-1 && grid[i][j+1] == "1") {
                    y = x+1;
                    uf.union(x, y);
                }
            }
        }
        return uf.count;
    }
}