8000 20201011 · BoscoSuen/leetcode@807695f · GitHub
[go: up one dir, main page]
Skip to content

Commit 807695f

Browse files
BoscoSuenBoscoSuen
committed
20201011
1 parent 2206ee3 commit 807695f

File tree

2 files changed

+138
-0
lines changed

2 files changed

+138
-0
lines changed

‎Java/839.similar-string-groups.java

Lines changed: 67 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,67 @@
1+
/*
2+
* @lc app=leetcode id=839 lang=java
3+
*
4+
* [839] Similar String Groups
5+
*/
6+
7+
// @lc code=start
8+
class Solution {
9+
/*
10+
time: O(N^2 (max(W, log N)))
11+
space: O(n)
12+
*/
13+
class UF {
14+
int[] parent;
15+
int size;
16+
17+
public UF(int n) {
18+
parent = new int[n];
19+
for (int i = 0; i < n; ++i) {
20+
parent[i] = i;
21+
}
22+
size = n;
23+
}
24+
25+
private void union(int x, int y) {
26+
int px = find(x);
27+
int py = find(y);
28+
if (px != py) {
29+
parent[py] = px;
30+
size--;
31+
}
32+
}
33+
34+
private int find(int x) {
35+
while (parent[x] != x) {
36+
parent[x] = parent[parent[x]];
37+
x = parent[x];
38+
}
39+
return x;
40+
}
41+
}
42+
public int numSimilarGroups(String[] A) {
43+
if (A == null || A.length == 0) return 0;
44+
UF uf = new UF(A.length);
45+
for (int i = 0; i < A.length; ++i) {
46+
for (int j = i + 1; j < A.length; ++j) {
47+
if (isSimilar(A[i], A[j])) {
48+
uf.union(i, j);
49+
}
50+
}
51+
}
52+
return uf.size;
53+
}
54+
55+
private boolean isSimilar(String a, String b) {
56+
if (a.length() != b.length()) return false;
57+
int count = 0;
58+
for (int i= 0; i < a.length(); ++i) {
59+
if (a.charAt(i) != b.charAt(i) && ++count > 2) {
60+
return false;
61+
}
62+
}
63+
return true;
64+
}
65+
}
66+
// @lc code=end
67+

‎Java/924.minimize-malware-spread.java

Lines changed: 71 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,71 @@
1+
/*
2+
* @lc app=leetcode id=924 lang=java
3+
*
4+
* [924] Minimize Malware Spread
5+
*/
6+
7+
// @lc code=start
8+
class Solution {
9+
/*
10+
Union found all nodes.
11+
Count the union size of each union set.
12+
Count the malware number of each union set.
13+
14+
Return the biggest union's malware if there is one and only one malware.
15+
If no such union that has and has only one malware,
16+
return the malware with minimum index.
17+
time: O(n^2)
18+
*/
19+
public int minMalwareSpread(int[][] graph, int[] initial) {
20+
if (graph == null || graph.length == 0) return 0;
21+
int n = graph.length;
22+
int[] parent = new int[n];
23+
for (int i = 0; i < n; ++i) {
24+
parent[i] = i;
25+
}
26+
for (int i = 0; i < n; ++i) {
27+
for (int j = i + 1; j < n; ++j) {
28+
if (graph[i][j] == 1) {
29+
union(parent, i, j);
30+
}
31+
}
32+
}
33+
int[] ufSize = new int[n];
34+
int[] initCount = new int[n];
35+
for (int i = 0; i < n; ++i) {
36+
ufSize[find(parent, i)]++;
37+
}
38+
for (int init : initial) {
39+
initCount[find(parent, init)]++;
40+
}
41+
int res = -1;
42+
Arrays.sort(initial);
43+
int max = 0;
44+
for (int init : initial) {
45+
int root = find(parent, init);
46+
if (initCount[root] == 1 && ufSize[root] > max) {
47+
max = ufSize[root];
48+
res = init;
49+
}
50+
}
51+
return max == 0 ? initial[0] : res;
52+
}
53+
54+
private void union(int[] parent, int x, int y) {
55+
int px = find(parent, x);
56+
int py = find(parent, y);
57+
if (px != py) {
58+
parent[py] = px;
59+
}
60+
}
61+
62+
private int find(int[] parent, int x) {
63+
while (x != parent[x]) {
64+
parent[x] = parent[parent[x]];
65+
x = parent[x];
66+
}
67+
return x;
68+
}
69+
}
70+
// @lc code=end
71+

0 commit comments

Comments
 (0)
0