网络异常，图片无法展示
|
给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程
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 <= 500equations[i].length == 4equations[i][0]和equations[i][3]是小写字母equations[i][1]要么是'='，要么是'!'equations[i][2]是'='
解题思路
- 首先处理所有等式，将相等关系的变量放在一个集合中，如果两个变量已经分别属于一个集合，则要将两个集合合并。
- 然后处理所有不等式，如果当前两个变量处于同一个集合，则无法同时满足相等与不等，返回
false。 - 如果所有方程处理完成没有无法满足的方程，则返回
true。
对于需要频繁处理集合合并以及查询元素所处集合的问题，可以利用 并查集 解题。如果你对 并查集 还不了解，可以看我这一篇文章 数据结构-并查集,文中介绍了并查集的概念、应用场景以及手写实现的全过程。
代码实现
var equationsPossible = function(equations) { // 初始化map存储变量及集合关系 const map = new Map(), // 初始化不等式方程数组 notEqual = []; // 获取当前元素所在集合根节点方法 function find(x){ if(map.get(x)===x) return x; return find(map.get(x)) } // 循环输入数组 for(let i = 0;i<equations.length;i++){ const [a,symbol,,b] = equations[i] // 如果当前为不等式，将方程式放入不等式方程数组 if(symbol==='!'){ notEqual.push(equations[i]) }else{ // 如果集合中存储了a 和 b if(map.has(a)&&map.has(b)){ // 获取两个变量所在集合的根节点 const rootA = find(a), rootB = find(b); // 如果两个变量所处不同集合，合并集合 if(rootA!==rootB){ map.set(rootA,rootB); } // 如果 b 未存储，将 b 加入 a 所在集合 }else if(map.has(a)){ map.set(b,find(a)) // 如果 a 未存储，将 a 加入 b 所在集合 }else if(map.has(b)){ map.set(a,find(b)) }else{ // 如果都未存储，将 a b 存储在一个新集合 map.set(a,a) map.set(b,a) } } } // 遍历不等方程 for(let i = 0;i<notEqual.length;i++){ const [a,,,b] = notEqual[i]; // 如果两个变量为同一个变量，此时又是不等式，所以无法满足方程 if(a===b) return false; // 如果两个变量都被存储过，且所处相同集合，则无法满足方程 if(map.has(a)&&map.has(b)&&(find(a)===find(b))) return false; } // 所有方程都可以满足，返回 true return true; }; 复制代码
至此我们就完成了 leetcode-990-等式方程的可满足性
如有任何问题或建议，欢迎留言讨论！
