Re: [閒聊] 每日leetcode
剩我聖誕夜還在解題了
3203. Find Minimum Diameter After Merging Two Trees
思路
就將每棵樹的各個節點的indegree算出來
接著將indegree=1的節點丟到queue裡
從queue裡pop出indegree=1的節點
把與它相連的node indegree都-1
如果indegree=1且之前沒有遇到就push到queue裡
這樣可以算出這棵樹的level
如果最後一次queue的長度大於1
那就把level++
最後回傳level
再來去算兩棵樹各自兩點間相隔最長的路徑length1、length2
答案就會是max(level1+level2,length1,length2)
golang code :
func minimumDiameterAfterMerge(edges1 [][]int, edges2 [][]int) int {
indegree1, path1 := calindegree(edges1)
indegree2, path2 := calindegree(edges2)
level1, length1 := callevel(indegree1, path1)
level2, length2 := callevel(indegree2, path2)
return max(length1, length2, level1+level2+1)
}
func calindegree(edge [][]int) ([]int, [][]int) {
n := len(edge) + 1
res := make([]int, n)
path := make([][]int, n)
for i := 0; i < n; i++ {
path[i] = []int{}
}
for _, val := range edge {
res[val[0]]++
path[val[0]] = append(path[val[0]], val[1])
res[val[1]]++
path[val[1]] = append(path[val[1]], val[0])
}
return res, path
}
func callevel(indegree []int, path [][]int) (int, int) {
queue := []int{}
visit := make([]bool, len(indegree))
for key, val := range indegree {
if val == 1 {
queue = append(queue, key)
visit[key] = true
}
}
tmp := 0
level := -1
for len(queue) > 0 {
cnt := len(queue)
level++
tmp = cnt
for cnt > 0 {
node := queue[0]
queue = queue[1:]
for _, val := range path[node] {
indegree[val]--
if indegree[val] == 1 && !visit[val] {
queue = append(queue, val)
visit[val] = true
}
}
cnt--
}
}
length := (level) * 2
if tmp > 1 {
return level + 1, length + 1
}
if level == -1 {
return 0, 0
}
return level, length
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.71.213.2 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1735041857.A.B8B.html
推
12/24 20:05,
11月前
, 1F
12/24 20:05, 1F
→
12/24 20:08,
11月前
, 2F
12/24 20:08, 2F
討論串 (同標題文章)
完整討論串 (本文為第 1222 之 1554 篇)：