[数据结构与算法]990. 等式方程的可满足性(Java) LeeCode

解题思路：
查看一组方程式里面逻辑是否相通，利用合并集可以很直观的解决这个问题。
合并集：简单理解为表示两个节点直接是否连通。

class Solution {

    //动态连通性其实就是一种等价关系，具有「自反性」「传递性」和「对称性」，其实 == 关系也是一种等价关系，具有这些性质。所以这个问题用 Union-Find 算法就很自然
    public boolean equationsPossible(String[] equations) {

        UF uf = new UF(26);

        //先查看相等的情况等下，将相等的字符设置为连通
        for(String i : equations){
            if(i.charAt(1) == '='){
                char x = i.charAt(0);
                char y = i.charAt(3);
                uf.union(x - 'a', y - 'a'); //保持数值在26以内
            }
        }
        //再检查不相等的情况，此时如果是连通状态，那肯定是不合理的
        for (String i : equations){
            if (i.charAt(1) == '!'){
                char x = i.charAt(0);
                char y = i.charAt(3);

                if(uf.connected(x - 'a', y - 'a'))
                return false;
            }
        }
        return true;
    }
}

合并集 class:

class UF{

    //记录连通个数
    private int count;
    //节点 x 的节点是 parent[x] 
    private int[] parent;

    private int[] size; // 记录树的值，来体现节点值的大小，帮助后续平衡连接节点

    public UF(int n ){
        //一开始互不连通
        this.count = n;

        //父节点指针初始指向自己
        parent = new int[n];

        size = new int[n];
        for(int i = 0; i < n; i++){
            parent[i] = i;
            size[i] = 1; //初始化都应该为一
        }
    }

    public void union(int p, int q){
        int rootP = find(p);
        int rootQ = find(q);
        if(rootP == rootQ) return;

        //让树保持平衡，小数接在大树下面
        if(size[rootP] > size[rootQ]){
            parent[rootQ] = rootP; //谁大谁当根节点
            size[rootP] += size[rootQ];
        }else{
            parent[rootP] = rootQ;
            size[rootQ] += size[rootP];
        }
        count--;
    }

    public int find(int x){
        while(parent[x] != x){
            parent[x] = parent[parent[x]];
            x = parent[x]; //复杂度为1
        }
        
        return x;
    }

    // 判断节点 p 和节点 q 是否连通
    public boolean connected(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        return rootP == rootQ;
    }

    public int count(){
        return count;
    }
}

创作挑战赛

新人创作奖励来咯，坚持创作打卡瓜分现金大奖