990. 等式方程的可满足性
题目来源：力扣（LeetCode）https://leetcode-cn.com/problems/satisfiability-of-equality-equations
题目
给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 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] 是 '='
解题思路
思路：并查集
先看例 3 和 例 4。这两个例题中，所给不同部分就是数组中第二个方程式。看看例 4 中，为何返回的结果是 False？
["a==b","b!=c","c==a"]
在例 4 当中，第二个式子 b!=c，而前面的式子中 a==c 那么这里将 a 替换 b，第二个式子就变为 a!=c，但是最后的式子中 a==c 又成立，这里就明显存在冲突，所以这里结果返回 False。
在上面的例子当中，我们也可以看到，相等关系具有传递性，所有的相等变量其实是属于同一个集合。但是这里并不关心传递的距离，只关心是否连通。那么这里就考虑使用并查集来解决本问题。
这里，关于并查集设计算法具体如下：
- 首先构造并查集，遍历所有等式。每个等式的两个变量属于连通分量，将两者进行合并；
- 这里还需要再次遍历所有不等式，因为不等式的两个变量不属于同一个连通分量，这里两者不能合并，要分开查找对应的连通分量，这里有两种情况：
- 如果两个变量属于同个连通分量，那么就与原假设不符，存在矛盾，这里应该返回 False；
- 如果没有出现上面所述的矛盾，那么最终返回 True
在这里，我们可以将数组中方程式的变量当成节点，相等关系则表示两个节点的边。前面说明，相等变量属于同个连通分量，那么使用并查集来维护这个关系
具体的实现：
- 创建数组存储每个变量的连通分量，其中每个元素表示的是所在连通分量的父节点信息。如果父节点是自身，那么这个就是所在连通分量的根节点。
- 初始化的时候，将变量的父节点都指向自身。
- 查找操作：从当前变量的父节点往上找，直至找到根节点；
- 合并操作：将其中一个变量的根节点指向另外一个变量的根节点。
具体的代码实现如下。
代码实现
from typing import List
class Solution:
# 并查集类
class UnionFind(object):
def __init__(self):
'''初始化数组
'''
self.parent = list(range(26))
def find(self, index):
'''查询操作
查询直至根节点
这里使用了路径压缩
'''
# 如果父节点是自身，那么就是根节点，返回
while index!=self.parent[index]:
self.parent[index] = self.parent[self.parent[index]]
index = self.parent[index]
return index
def union(self, index1, index2):
'''合并操作
将其中一个变量的根节点指向另外一个变量的根节点
'''
root_index1 = self.find(index1)
root_index2 = self.find(index2)
self.parent[root_index1] = root_index2
def is_connected(self, index1, index2):
'''判断是否连通
'''
return self.find(index1) == self.find(index2)
def equationsPossible(self, equations: List[str]) -> bool:
uf = Solution.UnionFind()
# 第一次遍历所有等式，进行合并
for equation in equations:
if equation[1] == "=":
# 这里将变量字符转换为整数
# ord('a') 返回对应的十进制整数
index1 = ord(equation[0]) - ord('a')
index2 = ord(equation[3]) - ord('a')
uf.union(index1, index2)
# 再次遍历所有不等式，查找对应的连通分量
for equation in equations:
if equation[1] == '!':
index1 = ord(equation[0]) - ord('a')
index2 = ord(equation[3]) - ord('a')
# 如果两个变量属于同个连通分量，那就出现矛盾，返回 False
if uf.is_connected(index1, index2):
return False
# 最终没有矛盾，返回 True
return True
# equations = ["b==a","a==b"]
equations = ["a==b","b!=a"]
solution = Solution()
solution.equationsPossible(equations)
实现结果
实现结果
总结
- 通过题中示例，我们知道等式具有传递性。但是题中只关心连通性，并不关心传递的距离，所以我们考虑使用并查集的思路来解决问题。
- 关于并查集的算法设计流程：
- 首先构造并查集，先遍历所有的等式，因为两个变量这里属于同一个连通分量，那么将其进行合并
- 再次遍历 所有的不等式，在这里两个变量并不属于同个连通分量，那么不能进行合并，要各自查找对应的连通分量。如果这个时候出现两个变量的连通分量相同的情况，那么这个就跟前面的预设不符，出现矛盾。返回 False
- 如果没有出现上面所述的矛盾，那么返回 True。
以上就是关于解决《990. 等式方程的可满足性》问题的主要内容。如果觉得写得还不错，欢迎关注。微信公众号《书所集录》同步更新，同样欢迎关注。
网友评论