Re: [閒聊] 每日leetcode已回收

看板Marginalman作者Rushia (早瀬ユウカの体操服 )時間1年前 (2024/04/23 09:55)推噓2(2推 0噓 2→)

留言4則, 4人參與討論串150/1548 (看更多)

https://leetcode.com/problems/minimum-height-trees/description 310. Minimum Height Trees 給你一個數字 n 表示節點數，和一個表示邊關係的陣列 edges，如果把某個節點作為root 有最小的樹高，那麼他被稱為Minimum Height Tree(MHT)，求出所有的MHT根節點有哪些。思路: 1.最簡單的方法就是對編號0~n-1的所有頂點做BFS，然後留下高度最小的，但是他測資 2*10^4，我去死。 2.這題沒看過很難解出來，每個樹都有葉子節點，我們把所有非葉子節點匡起來： https://i.imgur.com/c7f3DyC.png

我們會發現從葉子節點出發一定不可能是MHT，因為他需要穿過中間圈起來的非葉節點再到另一邊的葉節點這樣就至少高度為3了，相反的，我們如果從非葉節點往外出發的話高度只為二，所以我們的目標就是找出紅色部分的節點有哪些。 3.我們將那些不可能是MHT的節點都刪除： https://i.imgur.com/gGG26HF.png

我們發現刪除後的圖一樣可以分成葉子節點和非葉節點。不斷的刪除葉子節點後，我們可以得到不存在非葉節點的圖： https://i.imgur.com/qoGraPm.png

這就是我們要找的MHT root。 4.實現方式大概就幾步：建圖 -> 算入度 -> 把入度為1(葉子節點)的節點加到queue BFS -> BFS時每次都把該點刪除並更新入度，如果刪除完的點入度為 1 就表示刪除後找到新的葉節點，放入 queue 不斷BFS -> 返回最後剩下的葉節點 5.你辛苦的寫完BFS送出之後馬上噴一個WA，因為 n=1 是 corner case 要直接返回 [0] (幹)。 py code: ------------------------------------------------ class Solution: def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]: if n == 1: return [0] degree = [0] * n graph = defaultdict(list) for edge in edges: degree[edge[0]] += 1 degree[edge[1]] += 1 graph[edge[0]].append(edge[1]) graph[edge[1]].append(edge[0]) q = deque() for id, x in enumerate(degree): if x == 1: q.append(id) res = [] while q: size = len(q) res = [] for i in range(size): x = q.popleft() res.append(x) for neighbor in graph[x]: degree[neighbor] -= 1 if degree[neighbor] == 1: q.append(neighbor) return res ------------------------------------------------ 極困難BFS 之前寫過一次重寫忘光光想了10分鐘看到n=2*10^4 果斷看之前寫的解= = -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.138.255.173 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1713837318.A.B8E.html

→

oinishere

04/23 09:58, 1年前 , 1^F

04/23 09:58, 1^F

推

argorok

04/23 10:10, 1年前 , 2^F

04/23 10:10, 2^F

→

DJYOSHITAKA

04/23 10:30, 1年前 , 3^F

04/23 10:30, 3^F