学习内容:

LeeCodeJava并查集

959.由斜杠划分区域(中等)

我的代码

class Solution {
    public int regionsBySlashes(String[] grid) {
        AndCollect andCollect= new AndCollect();
        AndCollect.L=grid.length;
        andCollect.resource=new int[AndCollect.L*AndCollect.L*4];
        Arrays.fill(andCollect.resource,-1);
        int a;
        for (int i = 0; i < AndCollect.L; i++) {
            int count=-1;
            for (int j = 0; j < grid[i].length(); j++) {
                count++;
                a=AndCollect.getIndex(i,count);
                switch (grid[i].charAt(j)){
                    case ' ':
                        for (int k = 0; k < 3; k++) {
                           andCollect.union(a,a+k+1);
                        }
                        break;
                    case '/':
                        andCollect.union(a,a+3);
                        andCollect.union(a+1,a+2);
                        break;
                    case '\\':
                        andCollect.union(a,a+1);
                        andCollect.union(a+2,a+3);
                        //CharAt()会直接跳过\\中的下一个\
                    default:
                        break;
                }
                if(count!=0){
                    andCollect.union(a-3,a+3);
                }
                if(i!=0){
                    andCollect.union(AndCollect.getIndex(i-1,count)+2,a);
                }
            }
        }
        int count=0;
        for (int i = 0; i < andCollect.resource.length; i++) {
            if(andCollect.resource[i]==-1){
                count++;
            }
        }
        return count;
    }
    static class AndCollect{
        int[] resource;
        static int L;
        public void union(int a, int b){
            int fa=find(a);
            int fb=find(b);
            if(!(fa==fb&&fa!=-1)){
                resource[fb]=fa;
            }
        }
        public int find(int a){
            while(resource[a]!=-1){
                a=resource[a];
            }
            return a;
        }
        /**@apiNote 获取目标方格的第一个三角*/
        static int getIndex(int lin,int cul){
            return (lin*L+cul)*4;
            //这里注意是每个格子占了四个位置.
        }
    }
}

思路:

通过将一个格子根据对角线分成四个三角形,将每个格子的四个三角形展开,化成一个一维数组,构成并查集,之后根据划线的状态,分别将对应的位置的集合进行划分操作,最后判断根节点一共有几个.

注意点:

1.在Java中’\‘视作一个字符,即’\’,在chatAt()中不需要另外操作.
2.应该注意,灵魂之处在于小三角的展开,这是将二维数组一维化形成并查集的关键.
3.不光需要格子内部的三角形之间的联系,也需要格子之间的联系,因为分隔是在格子之间分割的,所以相邻三角形之间可以无脑链接.

改进处

1.使用-1作为根节点的判定具有局限性,标准的并查集应当使用其本身的index作为值,以判断其是否为根节点.
2.尝试在find()处使用递归函数.

改进代码

class Solution {
    public int regionsBySlashes(String[] grid) {
        AndCollect andCollect= new AndCollect();
        AndCollect.L=grid.length;
        andCollect.resource=new int[AndCollect.L*AndCollect.L*4];
        for (int i = 0; i < andCollect.resource.length; i++) {
            andCollect.resource[i]=i;
        }
        int a;
        for (int i = 0; i < AndCollect.L; i++) {
            int count=-1;
            for (int j = 0; j < grid[i].length(); j++) {
                count++;
                a=AndCollect.getIndex(i,count);
                switch (grid[i].charAt(j)){
                    case ' ':
                        for (int k = 0; k < 3; k++) {
                           andCollect.union(a,a+k+1);
                        }
                        break;
                    case '/':
                        andCollect.union(a,a+3);
                        andCollect.union(a+1,a+2);
                        break;
                    case '\\':
                        andCollect.union(a,a+1);
                        andCollect.union(a+2,a+3);
                        //CharAt()会直接跳过\\中的下一个\
                    default:
                        break;
                }
                if(count!=0){
                    andCollect.union(a-3,a+3);
                }
                if(i!=0){
                    andCollect.union(AndCollect.getIndex(i-1,count)+2,a);
                }
            }
        }
        int count=0;
        for (int i = 0; i < andCollect.resource.length; i++) {
            if(andCollect.resource[i]==i){
                count++;
            }
        }
        return count;
    }
    static class AndCollect{
        int[] resource;
        static int L;
        public void union(int a, int b){
            int fa=find(a);
            int fb=find(b);
            if(fa!=fb){
                resource[fb]=fa;
            }
        }
        public int find(int a){
            if(resource[a]==a){
                return a;
            }else{
                return find(resource[a]);
            }
        }
        /**@apiNote 获取目标方格的第一个三角*/
        static int getIndex(int lin,int cul){
            return (lin*L+cul)*4;
            //这里注意是每个格子占了四个位置.
        }
    }
}

结果

减少了一点内存,将根节点改为其本身的index,相对来说可以减少逻辑的复杂程度,同时也可以让find()方法使用递归的方法,而不用担心内部死循环是一个值得记住的好习惯.

优解代码

class Solution {
    public int regionsBySlashes(String[] grid) {
    final int len = grid.length + 1;
    final DSU dus = new DSU(len * len);
    int t1 = len * (len - 1);
    //这个是让全图都与0相连接,或者说都与第一个连接
    for (int i = 0; i < len; i++) {
        dus.union(0, i);
        dus.union(0, i * len);
        dus.union(0, i + t1);
        dus.union(0, (i + 1) * len - 1);
    }
    int result = 1;
    for (int i = 0; i < len - 1; i++) {
        for (int j = 0; j < len - 1; j++) {
            char c = grid[i].charAt(j);
            int index = i * len + j + 1;
            if (c == '\\') {
                if (dus.union(index - 1, index + len)) result++;
            } else if (c == '/') {
                if (dus.union(index, index + len - 1)) result++;
            }
        }
    }
    return result;
}
class DSU {
    int[] temps;
    public DSU(int n) {
        temps = new int[n];
        for (int i = 0; i < n; i++) {
            temps[i] = i;
        }
    }
    public int find(int n) {
        if (temps[n] == n) return n;
        temps[n] = find(temps[n]);
        return temps[n];
    }
    public boolean union(int x, int y) {
        int tx = find(x);
        int ty = find(y);
        if (tx == ty) return true;
        temps[ty] = tx;
        return false;
    }
}

结论:

看不懂QAQ