Union Find
990
[LC 990](990. Satisfiability of Equality Equations)
滿足所有等式
ex:
a==b, b==a return true
ex2:
a!=b, b==a return false
ex3:
a==b, a==c, b!=c return false
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
class Solution {
private int[] groups = new int[26];
public boolean equationsPossible(String[] equations) {
for(int i = 0; i < 26; i++) {
groups[i] = i;
}
for(String s : equations) {
if(s.charAt(1) == '=') {
union(s.charAt(0), s.charAt(3));
}
}
for(String s : equations) {
if(s.charAt(1) == '!') {
if(find(s.charAt(0) - 'a') == find(s.charAt(3) - 'a')) return false;
}
}
return true;
}
private void union(Character a, Character b) {
groups[find(a -'a')] = groups[find(b - 'a')];
}
private int find(int x) {
if(x == groups[x]) return x;
return groups[x] = find(groups[x]);
}
}
|
2275
[LC 2275](2275. Largest Combination With Bitwise AND Greater Than Zero)
Others
547
200
684
1319
399
952