Amazon sells books, every book has books which are strongly associated with it. Given ListA and ListB,indicates that ListA [i] is associated with ListB [i] which represents the book and associated books. Output the largest set associated with each other(output in any sort). You can assume that there is only one of the largest set.
A bookToID map
A ans map
class UF{
int[] parent;
int[] size;
public UF(int n){
parent = new int[n];
size = new int[n];
for(int i=0; i<n; i++){
parent[i] = i;
size[i] = 1;
}
}
public int find(int x){
if(parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
public void union(int x, int y){
int root_x = find(x);
int root_y = find(y);
if(root_x == root_y) return;
if(size[root_x] < size[root_y]){
parent[root_x] = root_y;
size[root_y] += size[root_x];
}else{
parent[root_y] = root_x;
size[root_x] += size[root_y];
}
}
}
public class Solution {
public List<String> maximumAssociationSet(String[] ListA, String[] ListB) {
UF uf = new UF(5000);
Map<String, Integer> bookToID = new HashMap<>();
int id=0;
for(int i=0; i<ListA.length; i++){
if(!bookToID.containsKey(ListA[i])) bookToID.put(ListA[i], id++);
if(!bookToID.containsKey(ListB[i])) bookToID.put(ListB[i], id++);
uf.union(bookToID.get(ListA[i]), bookToID.get(ListB[i]));
}
Map<Integer, List<String>> ans = new HashMap<>();
for(Map.Entry<String, Integer> entry: bookToID.entrySet()){
int root = uf.find(entry.getValue());
if(!ans.containsKey(root)) ans.put(root, new ArrayList<String>());
ans.get(root).add(entry.getKey());
}
int max=0;
List<String> result = new ArrayList<>();
for(List<String> list: ans.values()){
if(list.size()>max){
max = list.size();
result = list;
}
}
return result;
}
}
721. Accounts Merge
Given a list accounts, each element accounts[i] is a list of strings, where the first element accounts[i][0] is a name, and the rest of the elements are emails representing emails of the account. Now, we would like to merge these accounts. Two accounts definitely belong to the same person if there is some email that is common to both accounts. Return the email in sorted order
An emailToID map
An emailToName map
An ans map
Use EmailToName to update the answer
class UF:
def __init__(self):
self.p = [i for i in range(10000)]
def find(self, x):
if x != self.p[x]: self.p[x] = self.find(self.p[x])
return self.p[x]
def union(self, x1, x2):
self.p[self.find(x1)] = self.find(x2)
class Solution:
def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
uf = UF()
email_to_id = {}
email_to_name = {}
i = 0
for acc in accounts:
name = acc[0]
for email in acc[1:]:
email_to_name[email] = name
if email not in email_to_id:
email_to_id[email] = i
i+=1
uf.union(email_to_id[acc[1]], email_to_id[email])
ans = collections.defaultdict(list)
for email, id in email_to_id.items():
ans[uf.find(id)].append(email)
return [[email_to_name[li[0]]] + sorted(li) for li in ans.values()]
684. Redundant Connection
Undirect graph, use union- find
class UF:
def __init__(self):
self.p = [i for i in range(1001)]
def find(self, x):
if x != self.p[x]: self.p[x] = self.find(self.p[x])
return self.p[x]
def union(self, x1, x2):
self.p[self.find(x1)] = self.find(x2)
class Solution:
def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
uf = UF()
ans = None
for e in edges:
if uf.find(e[0]) == uf.find(e[1]):
ans = e
uf.union(e[0], e[1])
return ans
685. Redundant Connection II
Direct Graph
"""
根據parent做出判斷
1. p_a != p_b
if p_b != e[1]: node的parent不是自己，已經有其他parent -> multiple parents
不做union, 先保留答案
else: union a and b
2. p_a == p_b: cycle
如果兩個條件都符合，代表第一個parent先出現了，並且造成cycle所以有兩個candidate
找到e[1]的第一個parent
Example:[[2,1],[3,1],[4,2],[1,4]]
"""
class UF:
def __init__(self):
self.p = [i for i in range(1001)]
def find(self, x):
if x != self.p[x]: self.p[x] = self.find(self.p[x])
return self.p[x]
# 注意有方向關係，x2的parent要指向x1
def union(self, x1, x2):
self.p[self.find(x2)] = self.find(x1)
class Solution:
def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:
uf = UF()
cand1 = None
cand2 = None
for e in edges:
if uf.find(e[0]) != uf.find(e[1]):
if uf.find(e[1]) != e[1]:
cand1 = e
else:
uf.union(e[0], e[1])
else:
cand2 = e
if not cand2: return cand1
if not cand1: return cand2
for e in edges:
if e[1] == cand1[1]:
return e
return []
1202. Smallest String With Swap
Input: s = "dcab", pairs = [[0,3],[1,2],[0,2]]
Output: "abcd"
Explaination:
Swap s[0] and s[3], s = "bcad"
Swap s[0] and s[2], s = "acbd"
Swap s[1] and s[2], s = "abcd"
"""
[0, 1], [1, 2] -> [0, 1, 2] 代表這中間的c皆可互換
sort the character array, 並依序把ch指派到idx上
"""
class UF:
def __init__(self, n):
self.p = list(range(n))
def find(self, x):
if x != self.p[x]: self.p[x] = self.find(self.p[x])
return self.p[x]
def union(self, x, y):
self.p[self.find(x)] = self.find(y)
class Solution:
def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
n = len(s)
uf = UF(n)
group = defaultdict(list)
# union index
for p in pairs:
uf.union(p[0], p[1])
# record the characters in the same group
for idx in range(n):
group[uf.find(idx)].append(s[idx])
# sort the characters
for v in group.values():
v.sort()
build = []
# put the character but sequence
for idx in range(n):
build.append(group[uf.find(idx)].pop(0))
return ''.join(build)
924. Minimize Malware Spread
In a network of nodes, each node i is directly connected to another node j if and only if graph[i][j] = 1. Some nodes initial are initially infected by malware. We will remove one node from the initial list. Return the node that if removed, would minimize the affected nodes
Need to know size of the each init group
If there are 2 inits in group, then it will eventually effected no matter remove any of the node
Update when 1. group size is bigger 2. Same size but with smaller index
class DSU:
def __init__(self, n):
self.p = [i for i in range(n)]
self.size = [1] * n
def find(self, x):
if x != self.p[x]: self.p[x] = self.find(self.p[x])
return self.p[x]
def union(self, x, y):
xp, yp = self.find(x), self.find(y)
if xp == yp: return
self.p[xp] = yp
self.size[yp] += self.size[xp]
def getSize(self, x):
return self.size[self.find(x)]
class Solution:
def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
n = len(graph)
dsu = DSU(n)
# union connected nodes
for i in range(n):
for j in range(i):
if graph[i][j] == 1:
dsu.union(i, j)
# check if init in same set
uniqueCount = collections.defaultdict(int)
for init in initial:
uniqueCount[dsu.find(init)] += 1
ans = -1
for init in initial:
if uniqueCount[dsu.find(init)] == 1: # the union only has 1 init
if ans == -1:
ans = init
elif dsu.getSize(init) > dsu.getSize(ans):
ans = init
elif dsu.getSize(init) == dsu.getSize(ans) and init < ans:
ans = init
return ans if ans != -1 else min(initial)