不知这里有没有高手有参加这周的Leetcode 周赛,想请教leetcode 2029
https://leetcode.com/problems/find-all-people-with-secret/
这题我是用Union-Find来做的,思路大致是:
先用一个dictionary把同一个时间的meeting放在一起,然后由时间小的loop到时间大的
如果该meeting中的参与人x, y中有一个和firstPerson是同一个根节点,则union
在每一个union操作后,将x, y皆放入res
同个时间若有多个meeting,则用一个while loop,不断检查该时间的所有x, y组合
直至res不再变动
以下是我的code,我一直想不透错在哪,到第38个test case时fail了
class Solution(object):
def findAllPeople(self, n, meetings, firstPerson):
"""
:type n: int
:type meetings: List[List[int]]
:type firstPerson: int
:rtype: List[int]
"""
parent = {i: i for i in range(n)}
res = set()
res.add(0)
res.add(firstPerson)
def find(x):
if x != parent[x]:
parent[x] = find(parent[x])
return parent[x]
def union(a, b):
pa, pb = find(a), find(b)
if pa!=pb:
parent[pa] = pb
union(0, firstPerson)
hmap = collections.defaultdict(list)
for a, b, time in meetings:
hmap[time].append((a, b))
for time in sorted(hmap.keys()):
arr = hmap[time]
while True:
tmp = res
for a, b in arr:
if find(a) == find(firstPerson) or find(b) ==
find(firstPerson):
union(a,b)
res.add(a)
res.add(b)
if tmp == res:
break
return list(res)
感谢各位愿意看完