学习内容

LeeCodeJava并查集

778.水位上升的泳池中游泳

思路:

使用并查集.动用一个while循环,每次将水位不足某个特定值的数据进行合并.随后查询右下角的根值是否与左上角的相等,相等则跳出.

我的代码:

class Solution {
    public int swimInWater(int[][] grid) {
        int time=0;
        int h=grid[0].length;
        UnionFind unionFind=new UnionFind(grid.length*h);
        while(true){
            for (int i = 0; i < grid.length; i++) {
                for (int j = 0; j < h; j++) {
                    if(grid[i][j]>time){
                        continue;
                    }
                    int temp=i*h+j;
                    if(i!=0&&grid[i-1][j]<=time){
                        unionFind.Union(temp-h,temp);
                    }
                    if(i!= grid.length-1&&grid[i+1][j]<=time){
                        unionFind.Union(temp,temp+h);
                    }
                    if(j!=0&&grid[i][j-1]<=time){
                        unionFind.Union(temp-1,temp);
                    }
                    if(j!=h-1&&grid[i][j+1]<=time){
                        unionFind.Union(temp,temp+1);
                    }
                }
            }
            if(unionFind.parent[0]==unionFind.parent[grid.length*h-1]){
                break;
            }
            time++;
        }
        return time;
    }
}
class UnionFind{
    int[] parent;
    //int[] size;
    int n;
    //int sizeCount;
    public UnionFind(int n) {
        this.n = n;
        parent=new int[n];
        for (int i = 0; i < parent.length; i++) {
            parent[i]=i;
        }
    }
    public int findParent(int target){
        if(target==parent[target]){
            return target;
        }else{
            return findParent(parent[target]);
        }
    }
    public void Union(int a,int b){
        a=findParent(a);
        b=findParent(b);
        if(a!=b){
            parent[b]=a;
        }
    }
}

结果:

超过时间限制
应该是不能使用多次的find_parent.
题目当中水位必定是从0开始,且必定是在最高点结束.

优解代码

public class Solution {
    private int N;
    public static final int[][] DIRECTIONS = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    public int swimInWater(int[][] grid) {
        this.N = grid.length;
        int len = N * N;
        // 下标：方格的高度，值：对应在方格中的坐标
        int[] index = new int[len];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                index[grid[i][j]] = getIndex(i, j);
                //将坐标放入高度的哈希表
            }
        }
        UnionFind unionFind = new UnionFind(len);
        for (int i = 0; i < len; i++) {
            int x = index[i] / N;
            int y = index[i] % N;
            for (int[] direction : DIRECTIONS) {
                int newX = x + direction[0];
                int newY = y + direction[1];
                if (inArea(newX, newY) && grid[newX][newY] <= i) {
                    unionFind.union(index[i], getIndex(newX, newY));
                }
                if (unionFind.isConnected(0, len - 1)) {
                    return i;
                }
            }
        }
        return -1;
    }
    private int getIndex(int x, int y) {
        return x * N + y;
    }
    private boolean inArea(int x, int y) {
        return x >= 0 && x < N && y >= 0 && y < N;
    }
    private class UnionFind {
        private int[] parent;
        public UnionFind(int n) {
            this.parent = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }
        public int root(int x) {
            while (x != parent[x]) {
                parent[x] = parent[parent[x]];
                x = parent[x];
            }
            return x;
        }
        public boolean isConnected(int x, int y) {
            return root(x) == root(y);
        }
        public void union(int p, int q) {
            if (isConnected(p, q)) {
                return;
            }
            parent[root(p)] = root(q);
        }
    }
}

心得

1.将二维数组缓存为一维数组有利于减少遍历时的内存耗费
2.尽量减少在循环内部的运算,比较.
3.并查集的最终并不是要求内部的值为同一个,而是要求root(a)==root(b)即可
4.这个方法只需要双重循环的要点是其只关注目前最小高度的那个点,刚好可以将高度最低的几个点连接在一起.我的三重循环方法,虽然会在有重复权值的平台高度的情况下有优势,但是很可惜这里没有涉及.