LeetCode之等式方程的可满足性

题目

给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 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] 是 '='
通过次数43,917提交次数83,897

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/satisfiability-of-equality-equations
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

一开始没有什么思路，然后查看了题解，基本上都是用并查集求解的。于是也试着用并查集写了下。

核心思想就是：

• 将相等的元素放在同一个集合中
• 查询不相等的顶点是否属于同一个集合，如果是，直接返回False，如果所有的都不是，才返回True

所以我这里定义了两个基本的方法，分别用于查找和合并：

查找：

# 找到当前元素属于哪个集合，并返回那个集合的索引位置
    def find(self, k: str, set_li):

        for i in range(len(set_li)):
            if k in set_li[i]:
                return i
        else:
            return None  # 不属于任何集合

合并：

 # 如果两个集合有交集就将它们合并
    def union(self, k1, k2, li: list):
        if li[k1] & li[k2]:
            li[k1] = li[k1] | li[k2]
            li.remove(li[k2])
            return True
        return False

整个思想就是：

1.先遍历整个equations列表，如果是等式，就将等式两边的变量添加(新建)到对应的集合；如果是不等式，就添加到一个不等式集合；

2.遍历不等式集合，查找不等式两边的变量是否在同一个等式集合中，如果在，直接返回False，如果都不在才返回True。

 

 

源码

from typing import List

class Solution:
    def equationsPossible(self, equations: List[str]) -> bool:
        # 把相等的顶点合并到同一个集合中
        # 查询两个顶点是否属于同一个集合
        equal_set_li = [set()]  # 用于存储相同的元素的集合
        tmp_not_equal_set = set()  # 用于存储不等式
        for equation in equations:
            if equation[1] == '=':
                i = self.find(equation[0], equal_set_li) or self.find(equation[-1], equal_set_li)  # 查询当前元素所在集合的位置
                if i != None:  # 找到了
                    equal_set_li[i].add(equation[0])
                    equal_set_li[i].add(equation[-1])
                    # 合并
                    for k in range(len(equal_set_li)):
                        if k != i:
                            union_flag = self.union(k, i, equal_set_li)
                            if union_flag:
                                break
                else:
                    equal_set_li.append({equation[0], equation[-1]})

            else:
                if equation[0] == equation[-1]: return False
                tmp_not_equal_set.add(equation)

        # 判断两个字母是否在同一个集合中
        for tmp in tmp_not_equal_set:
            tmp_k1 = self.find(tmp[0], equal_set_li)
            tmp_k2 = self.find(tmp[-1], equal_set_li)
            # print(tmp_k1, tmp_k2)
            if tmp_k1 and tmp_k2 and tmp_k1 == tmp_k2: return False
        else:
            return True

    # 找到当前元素属于哪个集合，并返回那个集合的索引位置
    def find(self, k: str, set_li):

        for i in range(len(set_li)):
            if k in set_li[i]:
                return i
        else:
            return None  # 不属于任何集合

    # 如果两个集合有交集就将它们合并
    def union(self, k1, k2, li: list):
        if li[k1] & li[k2]:
            li[k1] = li[k1] | li[k2]
            li.remove(li[k2])
            return True
        return False

通过截图

 

同步更新于个人博客系统：LeetCode之等式方程的可满足性