Re: [閒聊] 每日leetcode
懶得寫
講一下思路討論一下
dfs找每一個root
超過最小樹高直接break
還可以加碼dp紀錄每個節點的最長樹高
有料嗎
※ 引述 《Rushia (早瀬ユウカの体操服)》 之銘言：
:
: https://leetcode.com/problems/minimum-height-trees/description
: 310. Minimum Height Trees
: 給你一個數字 n 表示節點數，和一個表示邊關係的陣列 edges，如果把某個節點作為roo
t
: 有最小的樹高，那麼他被稱為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
: 這就是我們要找的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), 來自: 42.73.107.180 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1713837890.A.073.html
→
04/23 10:12,
4周前
, 1F
04/23 10:12, 1F
→
04/23 10:16,
4周前
, 2F
04/23 10:16, 2F
討論串 (同標題文章)
