原题
给定一个由表示变量之间关系的字符串方程组成的数组,每个字符串方程 equations[i]
的长度为 4
,并采用两种不同的形式之一:"a==b"
或 "a!=b"
。在这里,a 和 b 是小写字母(不一定不同),表示单字母变量名。
只有当可以将整数分配给变量名,以便满足所有给定的方程时才返回 true
,否则返回 false
。
示例 1:
输入: ["ab","b!=a"] 输出: false
解释: 如果我们指定,a = 1 且 b = 1,那么可以满足第一个方程,但无法满足第二个方程。没有办法分配变量同时满足这两个方程。
示例 2:
输入: ["ba","ab"] 输出: true
说明: 我们可以指定 a = 1 且 b = 1 以满足满足这两个方程。
示例 3:
输入: ["ab","bc","ac"] 输出: true
示例 4:
输入: ["ab","b!=c","ca"] 输出: false
示例 5:
输入: ["cc","bd","x!=z"] 输出: true
提示:
1 <= equations.length <= 500
equations[i].length == 4
equations[i][0]
和equations[i][3]
是小写字母equations[i][1]
要么是'='
,要么是'!'
equations[i][2]
是'='
解法
本题解同步发于leetcode题解:简洁的Java并查集
思想
见代码部分
代码
我写的这个代码没有任何优化但是很简洁,使用的HashMap实现的并查集(如果不了解并查集建议先去学习一下哦,还是蛮实用的一个数据结构的)
比较重要的思路是一定要先将字符串方程按相等到不等来排序,相等的方程用于建立并查集,不等的方程用于判断是否出错(即不等的两个代数是否出现在了同一个集合中)。
class Solution {
public boolean equationsPossible(String[] equations) {
// 并查集
Map<Character,Character> father = new HashMap<>();
// 先将字符串方程从相等到不等排序
Arrays.sort(equations,(s1,s2)->{
if(s1.charAt(1)==s2.charAt(1)) return 0;
return s1.charAt(1)=='='?-1:1;
});
for(String s:equations){
char[] chars = s.toCharArray();
char first = chars[0];
char second = chars[3];
// 获取根代表
while(father.containsKey(first) ) first = father.get(first);
while(father.containsKey(second)) second = father.get(second);
// 如果是不等,但根代表相同,说明出错
if(chars[1] == '!'){
if(first == second) return false;
// 如果是相等,跳过根代表相同的情况,把一个根代表连接到另一个根代表上(合并集合)
}else{
if(first == second) continue;
father.put(first, second);
}
}
return true;
}
}
刚看了下官方的题解并没有先排序,而是进行了两次遍历,第一次处理相等的,第二次处理不等的,确实比我写的时间复杂度要好,那么按这个思路修改之后就是:
class Solution {
public boolean equationsPossible(String[] equations) {
Map<Character,Character> father = new HashMap<>();
//建立并查集
for(String s:equations){
char[] chars = s.toCharArray();
if(chars[1] == '='){
char first = chars[0];
char second = chars[3];
while(father.containsKey(first) ) first = father.get(first);
while(father.containsKey(second)) second = father.get(second);
if(first == second) continue;
father.put(first, second);
}
}
//检查是否有错
for(String s:equations){
char[] chars = s.toCharArray();
if(chars[1] == '!'){
char first = chars[0];
char second = chars[3];
while(father.containsKey(first) ) first = father.get(first);
while(father.containsKey(second)) second = father.get(second);
if(first == second) return false;
}
}
return true;
}
}
可以发现有一些重复代码,如果抽取成一个函数会更简洁,还有哈希集可以写成数组,时间成本会更低一些,感兴趣的小伙伴自己试试优化啦(^_^)。
原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode990-%e7%ad%89%e5%bc%8f%e6%96%b9%e7%a8%8b%e7%9a%84%e5%8f%af%e6%bb%a1%e8%b6%b3%e6%80%a7/