LeetCode 990. 等式方程的可满足性 题目描述：给定一个由字符串数组组成的方程，每个方程 equations[i] 长度为 4，如 "a==b" 或 "a!=b" 。其中， a 和 b 是小写字母，表示单个字母的变量名。如果可以通过给变量分配整数，使得所有等式方程同时成立，则返回 true ，否则返回 false 。 1. 问题理解与抽象 方程只有两种形式：相等（ == ）和不等（ != ）。变量是 26 个小写字母。我们需要判断是否存在一种给每个变量赋值（如整数）的方式，使得所有等式同时满足。 本质上，这是一个 等价关系 的满足性问题：相等的变量必须属于同一个集合（取值相同），不等的变量必须属于不同集合（取值不同）。因此，我们可以将问题建模为 并查集 （Union-Find）问题。 2. 核心思路 将 26 个字母看作 26 个节点，初始时每个节点独立。 遍历所有等式方程，将每个相等关系 "a==b" 中的两个变量合并到同一个集合中。 然后遍历所有不等式方程 "a!=b" ，检查两个变量是否在同一个集合中。如果在，则与不等式矛盾，返回 false 。 如果所有不等式检查都通过，返回 true 。 3. 并查集设计 我们使用标准的并查集，包含： parent 数组，大小为 26， parent[i] 表示字母 'a'+i 的父节点索引。初始时 parent[i] = i 。 find(x) 函数：找到 x 的根节点（代表元素），同时进行路径压缩。 union(x, y) 函数：将 x 和 y 所在的集合合并。 4. 详细步骤 (a) 初始化 创建 parent 数组，索引 0~25 对应字母 'a'~'z'。初始时每个节点的父节点是自己。 (b) 处理所有等式 遍历 equations，对于每个 equation ： 如果 equation[ 1] 是 '=' （注意题目中是 "==" ，但长度 4 的字符串中第二个字符是 '='），则表示相等关系。 提取两个变量： x = equation[0] ， y = equation[3] 。 转换为索引： idx1 = x - 'a' ， idx2 = y - 'a' 。 在并查集中合并 idx1 和 idx2 。 (c) 处理所有不等式 再次遍历 equations，对于每个 equation ： 如果 equation[ 1] 是 '!' ，则表示不等关系。 提取变量并转换为索引 idx1 和 idx2 。 在并查集中查找 idx1 和 idx2 的根节点。 如果根节点相同，说明在同一个集合中，但这里要求不等，矛盾，直接返回 false 。 (d) 最终判断 如果所有不等式检查都通过，返回 true 。 5. 举例说明 例1： ["a==b", "b!=a"] 初始化：a(0), b(1) 各自独立。 处理等式 "a==b"：合并 a 和 b，现在 a 和 b 在同一个集合。 处理不等式 "b!=a"：查找 a 和 b 的根相同，矛盾，返回 false 。 例2： ["a==b", "b==c", "c!=a"] 处理等式 "a==b"：合并 a, b。 处理等式 "b==c"：合并 b, c，此时 a, b, c 在同一个集合。 处理不等式 "c!=a"：查找 a 和 c 的根相同，矛盾，返回 false 。 例3： ["c==c", "f!=a", "f==c", "a==c"] 处理等式 "c==c"：相同变量，不影响。 处理等式 "f==c"：合并 f, c。 处理等式 "a==c"：合并 a, c，此时 a, c, f 在同一个集合。 处理不等式 "f!=a"：查找 f 和 a 的根相同，矛盾，返回 false 。 6. 复杂度分析 时间复杂度：O(n + C α(C))，其中 n 是方程数量，C=26 是字母数，α 是阿克曼函数的反函数，可看作常数。 空间复杂度：O(C)，用于 parent 数组。 7. 关键点 先处理所有等式，构建等价集合。 再处理不等式，检查是否矛盾。 并查集的路径压缩和按秩合并（本题简单实现可以不按秩合并，因为只有 26 个节点）。