Re: [閒聊] 每日leetcode已回收
這題好難，偷看了一下解答
我這輩子就這樣了
310. Minimum Height Trees
有一個無向圖，兩個節點間只有一條路徑
該圖有n個節點:0~n-1，以及n-1條路徑
去找最小高度樹，並回傳所有最小高度樹的root
思路 :
首先葉子節點不可能是MHT的root
原因可以看這篇 : https://home.gamer.com.tw/artwork.php?sn=5478747
所以就從葉子節點開始去除
並記錄這麼做後有哪些節點變成葉子節點
這樣一直做之後
最後變成葉子節點的節點就是MHT的root
golang code:
func findMinHeightTrees(n int, edges [][]int) []int {
count:=make([]int,n)
link:=make([]int,n)
for _,val:=range edges{
//a^0=a
link[val[0]]^=val[1]//紀錄連接的點
count[val[0]]++
link[val[1]]^=val[0]//紀錄連接的點
count[val[1]]++
}
queue:=[]int{}
for key,val:=range count{
if val==1{
queue=append(queue,key)
}
}
step:=1
dist:=make([]int,n)
cnt:=len(queue)
maxdist:=0
for len(queue)>0{
for cnt>0{
//葉子節點 只有一個連接node,所以link[temp]就是與該葉子節點連接的節
點
temp:=queue[0]
queue=queue[1:]
//把與該葉子節點連結的節點link記錄去除該葉子節點
//(a^b^c)^a=(b^c)
link[link[temp]]^=temp
count[link[temp]]--
if count[link[temp]]==1{
queue=append(queue,link[temp])
dist[link[temp]]=max(dist[link[temp]],step)
}
cnt--
}
cnt=len(queue)
step++
}
for _,val:=range dist{
maxdist=max(maxdist,val)
}
res:=[]int{}
for key,val:=range dist{
if val==maxdist{
res=append(res,key)
}
}
return res
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.73.51.172 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1713871821.A.D3C.html
→
04/23 19:32,
1年前
, 1F
04/23 19:32, 1F
→
04/23 19:34,
1年前
, 2F
04/23 19:34, 2F
討論串 (同標題文章)
完整討論串 (本文為第 152 之 1548 篇)：