Union-Find, 并查集应用

Graph Valid Tree

• 开始做题之前，要注意先把定义和可能的各种 test case 正确输出弄清楚。在 LeetCode 上就只能反复提交试错，但是面试的时候，做题之前这些都是要通过交流去问清楚的，要么后面会浪费很多时间去涂涂改改，甚至发现一开始就答错了。。

给定一个 Set of Nodes ，Tree 要满足两个条件：

• 无环

• 单 root 节点

把这两点搞清楚之后，这题就很简单了。先一个一个 edge 去加，如果发现有环的话直接返回 false；否则跑到最后，看看最终的 number of connected components 是不是 1.

public class Solution {
    private class WeightedUnionFind{
        HashMap<Integer, Integer> parent;
        HashMap<Integer, Integer> size;
        boolean hasCycle;
        int count;

        public WeightedUnionFind(int n){
            parent = new HashMap<Integer, Integer>();
            size = new HashMap<Integer, Integer>();
            hasCycle = false;
            count = n;

            for(int i = 0; i < n; i++){
                parent.put(i, i);
                size.put(i, 1);
            }
        }

        public Integer find(Integer node){
            if(!parent.containsKey(node)) return null;
            Integer root = node;
            while(root != parent.get(root)){
                root = parent.get(root);
            }
            while(node != root){
                Integer next = parent.get(node);
                parent.put(node, root);
                node = next;
            }
            return root;
        }

        public void union(Integer nodeA, Integer nodeB){
            Integer rootA = find(nodeA);
            Integer rootB = find(nodeB);
            if(rootA == null || rootB == null) return;
            if(rootA.equals(rootB)) {
                hasCycle = true;
                return;
            }

            int sizeA = size.get(rootA);
            int sizeB = size.get(rootB);

            if(sizeA > sizeB){
                parent.put(rootB, rootA);
                size.put(rootA, sizeA + sizeB);
            } else {
                parent.put(rootA, rootB);
                size.put(rootB, sizeA + sizeB);
            }
            count --;
        }

        public boolean hasCycle(){
            return this.hasCycle;
        }

        public boolean isTree(){
            return (!this.hasCycle) && (count == 1);
        }

    }

    public boolean validTree(int n, int[][] edges) {
        if(edges == null || edges.length == 0){
            if(n > 1) return false;
            else return true;
        }

        WeightedUnionFind uf = new WeightedUnionFind(n);

        for(int i = 0; i < edges.length; i++){
            int nodeA = edges[i][0];
            int nodeB = edges[i][1];
            uf.union(nodeA, nodeB);
            if(uf.hasCycle()) return false;
        }

        return uf.isTree();
    }
}

Surrounded Regions

第一次写的时候用了个 HashSet 记录哪些点访问过，显得麻烦，还浪费了额外空间。

• 这种在矩阵上做 flood filling 的问题，可以靠自定义字符做标记，取代用额外空间的记录方式。

这段代码的逻辑就是从四个边开始碰到 'O' 就往里扫，把扫到的都标上 'S' 代表有效湖；最后过一遍的时候除了 'S' 的都标成 'X' 就好了。

然而在大矩阵上 stackoverflow... 看来无脑 dfs 的做法还不够经济啊。。。

public class Solution {
    public void solve(char[][] board) {
        if(board == null || board.length == 0) return;
        int rows = board.length;
        int cols = board[0].length;

        for(int i = 0; i < cols; i++){
            if(board[0][i] == 'O'){
                dfs(board, 0, i);
            }
            if(board[rows - 1][i] == 'O'){
                dfs(board, rows - 1, i);
            }
        }

        for(int i = 1; i < rows - 1; i++){
            if(board[i][0] == 'O'){
                dfs(board, i, 0);
            }
            if(board[i][cols - 1] == 'O'){
                dfs(board, i, cols - 1);
            }
        }

        for(int i = 0; i < rows; i++){
            for(int j = 0; j < cols; j++){
                if(board[i][j] == 'S'){
                    board[i][j] = 'O';
                } else {
                    board[i][j] = 'X';
                }
            }
        }

    }

    private void dfs(char[][] board, int row, int col){
        if(row < 0 || row >= board.length) return;
        if(col < 0 || col >= board[0].length) return;
        if(board[row][col] != 'O') return;

        board[row][col] = 'S';

        dfs(board, row + 1, col);
        dfs(board, row - 1, col);
        dfs(board, row, col + 1);
        dfs(board, row, col - 1);
    }
}

写了个 BFS 的在一个中型矩阵上 TLE了，我有点方。。

public class Solution {
    public void solve(char[][] board) {
        if(board == null || board.length == 0) return;
        int rows = board.length;
        int cols = board[0].length;
        Queue<Integer> queue = new LinkedList<Integer>();

        for(int i = 0; i < cols; i++){
            if(board[0][i] == 'O'){
                queue.offer(i);
                bfs(board, 0, i, queue);
            }
            if(board[rows - 1][i] == 'O'){
                queue.offer((rows - 1) * cols + i);
                bfs(board, rows - 1, i, queue);
            }
        }

        for(int i = 1; i < rows - 1; i++){
            if(board[i][0] == 'O'){
                queue.offer(i * cols);
                bfs(board, i, 0, queue);
            }
            if(board[i][cols - 1] == 'O'){
                queue.offer(i * cols + cols - 1);
                bfs(board, i, cols - 1, queue);
            }
        }

        for(int i = 0; i < rows; i++){
            for(int j = 0; j < cols; j++){
                if(board[i][j] == 'S'){
                    board[i][j] = 'O';
                } else {
                    board[i][j] = 'X';
                }
            }
        }

    }

    private void bfs(char[][] board, int row, int col, Queue<Integer> queue){
        int rows = board.length;
        int cols = board[0].length;

        if(!isValid(row, rows, col, cols)) return;

        while(!queue.isEmpty()){
            Integer index = queue.poll();
            int x = index / cols;
            int y = index % cols;
            if(board[x][y] == 'O') board[x][y] = 'S';

            if(isValid(x + 1, rows, y, cols) && board[x + 1][y] == 'O') queue.offer((x + 1) * cols + y);
            if(isValid(x - 1, rows, y, cols) && board[x - 1][y] == 'O') queue.offer((x - 1) * cols + y);
            if(isValid(x, rows, y + 1, cols) && board[x][y + 1] == 'O') queue.offer(x * cols + y + 1);
            if(isValid(x, rows, y - 1, cols) && board[x][y - 1] == 'O') queue.offer(x * cols + y - 1);
        }

        return;
    }

    private boolean isValid(int row, int rows, int col, int cols){
        if(row < 0 || row >= rows) return false;
        if(col < 0 || col >= cols) return false;
        return true;
    }
}

同样的 DFS 逻辑，做了如下改动之后就不会 stackoverflow 了：

• DFS 时不进入最外围一圈的位置

简单来讲是在尽可能限制 DFS call stack 的层数，控制 DFS 的深度。从正确性上讲，上面的写法也是正确的，但是在极端情况下如果某一个从边沿出发的 DFS 连通了另一个边沿出发的 DFS，会导致一次的搜索路径非常长，于是 stackoverflow. 既然边沿的格子无论如何都要检查一遍，就把外圈封住，减少每个起点的 search tree depth.

public class Solution {
    public void solve(char[][] board) {
        if(board == null || board.length == 0) return;
        int rows = board.length;
        int cols = board[0].length;

        for(int i = 0; i < cols; i++){
            if(board[0][i] == 'O'){
                dfs(board, 0, i);
            }
            if(board[rows - 1][i] == 'O'){
                dfs(board, rows - 1, i);
            }
        }

        for(int i = 1; i < rows - 1; i++){
            if(board[i][0] == 'O'){
                dfs(board, i, 0);
            }
            if(board[i][cols - 1] == 'O'){
                dfs(board, i, cols - 1);
            }
        }

        for(int i = 0; i < rows; i++){
            for(int j = 0; j < cols; j++){
                if(board[i][j] == 'S'){
                    board[i][j] = 'O';
                } else {
                    board[i][j] = 'X';
                }
            }
        }

    }

    private void dfs(char[][] board, int row, int col){
        if(row < 0 || row >= board.length) return;
        if(col < 0 || col >= board[0].length) return;

        if(board[row][col] != 'O') return;

        board[row][col] = 'S';

        // DFS 时不进入最外圈
        if(row + 2 < board.length && board[row + 1][col] == 'O') dfs(board, row + 1, col);
        if(row - 2 >= 0 && board[row - 1][col] == 'O') dfs(board, row - 1, col);
        if(col + 2 < board[0].length && board[row][col + 1] == 'O') dfs(board, row, col + 1);
        if(col - 2 >= 0 && board[row][col - 1] == 'O') dfs(board, row, col - 1);
    }
}

这题当然也可以用 Union-Find 写，先把所有最外圈的 boundry 连上，然后把里面的相邻 'O' 做 union，最后扫矩阵的时候，如果对应的 root 不是 boundry root 就留下，不然都改成 'X'.

不过只是在这个问题上，不是很简洁。