PTT數位生活區 / Python

[問題] leetcode 2029 (Hard) 的問題

看板Python作者 (薇薇安安)時間3年前 (2021/11/29 05:58), 編輯推噓10(10推 0噓 11→)
留言21則, 3人參與, 3年前最新討論串1/1
不知這裡有沒有高手有參加這週的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) 感謝各位願意看完 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 108.254.89.199 (美國) ※ 文章網址: https://www.ptt.cc/bbs/Python/M.1638136732.A.669.html
推
11/29 08:38, 3年前 , 1F
我猜是find(a) == find(firstPerson) or find(b)...這行
11/29 08:38, 1F
→
11/29 08:38, 3年前 , 2F
有可能迭代還沒完成但是tmp等於res
11/29 08:38, 2F
推
11/29 09:25, 3年前 , 3F
我是用一個set紀錄find(a), find(b)跟find(firstPerson)
11/29 09:25, 3F
→
11/29 09:27, 3年前 , 4F
每次循環結束檢查set長度，如果沒變就能跳出
11/29 09:27, 4F
→
11/29 09:33, 3年前 , 5F
問下，有可能迭代沒完成但res = tmp 嗎?
11/29 09:33, 5F
推
11/29 09:33, 3年前 , 6F
後來find的節點有機會讓之前find過的節點變更parent
11/29 09:33, 6F
→
11/29 09:34, 3年前 , 7F
最簡單的方式就是你的while True改成count跑個5次試試
11/29 09:34, 7F
推
11/29 09:37, 3年前 , 8F
不要tmp == res就break
11/29 09:37, 8F
→
11/29 09:48, 3年前 , 9F
查出問題了，tmp = res.copy()才對，不過會TLE
11/29 09:48, 9F
推
11/29 09:58, 3年前 , 10F
都忘了set也是淺拷貝XD
11/29 09:58, 10F
→
11/29 10:00, 3年前 , 11F
你的res會越來越大 TLE很正常吧
11/29 10:00, 11F
→
11/29 10:01, 3年前 , 12F
改成記長度之類的
11/29 10:01, 12F
推
11/29 10:09, 3年前 , 13F
有可能迭代沒完成但res = tmp 嗎? =>我想錯了 這不可能
11/29 10:09, 13F
推
11/29 10:36, 3年前 , 14F
提示: 同一個時段舉行的meeting仍然會洩漏秘密
11/29 10:36, 14F
推
11/29 10:43, 3年前 , 15F
提供一組測資，幫助你用來除錯。
11/29 10:43, 15F
→
11/29 10:43, 3年前 , 16F
11/29 10:43, 16F
推
11/29 10:45, 3年前 , 17F
11/29 10:45, 17F
推
11/29 10:50, 3年前 , 18F
不過原PO會把答案加到res 後面的人知道秘密就會加入res
11/29 10:50, 18F
→
11/29 10:50, 3年前 , 19F
所以res就跟一開始不一樣
11/29 10:50, 19F
→
11/29 12:39, 3年前 , 20F
謝謝，我已經懂了
11/29 12:39, 20F
→
11/29 12:55, 3年前 , 21F
這題蠻好的，值得一做
11/29 12:55, 21F
‣ 更多 VivianAnn 的文章
文章代碼(AID): #1Xe_kSPf (Python)
Python 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 VivianAnn 的文章
文章代碼(AID): #1Xe_kSPf (Python)