LeetCode之Satisfiability of Equal

问题：

方法：
很有意思的一道题，主要用到了Union-Find算法，需要先学习下这个算法。其中最主要的是find(input: Int)方法，可以找到联通节点中的根节点，同步还进行了路径压缩，所有联通节点都被压缩到只连接到根节点。最后根据等式进行联通和结果判断，最终就可以输出结果。

class SatisfiabilityOfEqualityEquations {
    private class UnionFind(n: Int) {
        private val parent: Array<Int> = Array(n) {
            it
        }

        fun find(input: Int): Int {
            var x = input
            while (x != parent[x]) {
                parent[x] = parent[parent[x]]
                x = parent[x]
            }
            return x
        }

        fun union(x:Int, y:Int) {
            val rootX = find(x)
            val rootY = find(y)
            parent[rootX] = rootY
        }

        fun isConnected(x: Int, y: Int): Boolean {
            return find(x) == find(y)
        }
    }

    fun equationsPossible(equations: Array<String>): Boolean {
        val unionFind = UnionFind(26)
        for (equation in equations) {
            if (equation[1] == '=') {
                val index1 = equation[0] - 'a'
                val index2 = equation[3] - 'a'
                unionFind.union(index1, index2)
            }
        }

        for (equation in equations) {
            if (equation[1] == '!') {
                val index1 = equation[0] - 'a'
                val index2 = equation[3] - 'a'

                if (unionFind.isConnected(index1, index2)) {
                    // 如果合并失败，表示等式有矛盾，根据题意，返回 false
                    return false
                }
            }
        }
        // 如果检查了所有不等式，都没有发现矛盾，返回 true
        return true
    }
}

fun main(args: Array<String>) {
    val equations = arrayOf("a==c","c==d","d!=a")
    val satisfiabilityOfEqualityEquations = SatisfiabilityOfEqualityEquations()
    println(satisfiabilityOfEqualityEquations.equationsPossible(equations))
}

有问题随时沟通

具体代码实现可以参考Github