【每日一题】- 2020-02-20 - 990. 等式方程的可满足性

[azl397985856]

给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 equations[i] 的长度为 4，并采用两种不同的形式之一："a==b" 或 "a!=b"。在这里，a 和 b 是小写字母（不一定不同），表示单字母变量名。

只有当可以将整数分配给变量名，以便满足所有给定的方程时才返回 true，否则返回 false。 

 

示例 1：

输入：["a==b","b!=a"]
输出：false
解释：如果我们指定，a = 1 且 b = 1，那么可以满足第一个方程，但无法满足第二个方程。没有办法分配变量同时满足这两个方程。
示例 2：

输出：["b==a","a==b"]
输入：true
解释：我们可以指定 a = 1 且 b = 1 以满足满足这两个方程。
示例 3：

输入：["a==b","b==c","a==c"]
输出：true
示例 4：

输入：["a==b","b!=c","c==a"]
输出：false
示例 5：

输入：["c==c","b==d","x!=z"]
输出：true
 

提示：

1 <= equations.length <= 500
equations[i].length == 4
equations[i][0] 和 equations[i][3] 是小写字母
equations[i][1] 要么是 '='，要么是 '!'
equations[i][2] 是 '='

[azl397985856]

【模板题】并查集（Python3）

关于并查集的题目不少，官方给的数据是30道（截止2020-02-20），但是有一些题目虽然官方没有贴并查集标签，但是使用并查集来说确非常简单。这类题目如果掌握模板，那么刷这种题会非常快，并且犯错的概率会大大降低，这就是模板的好处。

我这里总结了几道并查集的题目：

• 547.朋友圈
• 721. 账户合并

思路

并查集有一个重要的特征就是传导性，即A和B是连通的，B和C是连通的，那么A和C就是连通的。 是不是感觉和题目有点像？

题目中的 == 也一样具体传导性，因此我们的想法是基于 == 去 union 两个元素。 如果两个元素是连通的，并且 equation是 != 那么我们返回False，其他情况返回True

为了简单更加清晰，我将并查集模板代码单尽量独拿出来。

代码

find union connected 都是典型的模板代码。 然而我并没做计算连通分量，因此这道题根本不需要。 懂的同学可能也发现了，我没有做路径压缩，这直接导致find union connected 的时间复杂度最差的情况退化到$O(N)$。

当然优化也不难，我们只需要给每一个顶层元素设置一个size用来表示连通分量的大小，这样union的时候我们将小的拼接到大的上即可。 另外find的时候我们甚至可以路径压缩，将树高限定到常数，这样时间复杂度可以降低到$O(1)$。

class UF:
    parent = {}
    def __init__(self, equations):
        for eq in equations:
            self.parent[eq[0]] = eq[0]
            self.parent[eq[3]] = eq[3]
        
    def find(self, x):
        while x != self.parent[x]:
            x = self.parent[x]
        return x 
    def union(self, p, q):
        if self.connected(p, q): return
        self.parent[self.find(p)] = self.find(q)
    def connected(self, p, q):
        return self.find(p) == self.find(q)



class Solution:
    def equationsPossible(self, equations: List[str]) -> bool:
        uf = UF(equations)
        for eq in equations:
            if eq[1] == '=':
                uf.union(eq[0], eq[3])
        for eq in equations:
            if eq[1] == '!' and uf.connected(eq[0], eq[3]):
                return False
        return True

        

复杂度分析

• 时间复杂度：平均 $O(logN)$，最坏的情况是 O(N)$
• 空间复杂度：我们使用了 parent， 因此空间复杂度为 $O(N)$

相关专题

• 并查集专题

大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 36K star 啦。
大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

[stale]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.