Re: [閒聊] 每日leetcode
684. Redundant Connection
思路:
記錄每點出現在edges的次數
把出現1次的點抓出來丟到queue裡
接著從queue裡面抓點出來
並且扣掉跟他相連的點的次數
扣到剩1次後就丟到queue裡面
重複這個動作
最後只有組成cycle的點次數會是2
其他都會<=1
接著就從edges後面開始往回找，只要edges的兩點出現次數都是2
那就回傳該edge
golang code :
func findRedundantConnection(edges [][]int) []int {
n := len(edges)
path, degree := make([][]int, n+1), make([]int, n+1)
for _, val := range edges {
degree[val[1]]++
degree[val[0]]++
path[val[0]] = append(path[val[0]], val[1])
path[val[1]] = append(path[val[1]], val[0])
}
queue := []int{}
for key, val := range degree {
if val == 1 {
queue = append(queue, key)
}
}
for len(queue) > 0 {
curNode := queue[0]
queue = queue[1:]
for _, val := range path[curNode] {
degree[val]--
if degree[val] == 1 {
queue = append(queue, val)
}
}
}
for i := n - 1; i > -1; i-- {
if degree[edges[i][0]] == 2 && degree[edges[i][1]] == 2 {
return edges[i]
}
}
return nil
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.83.38.32 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1738142793.A.575.html
討論串 (同標題文章)
完整討論串 (本文為第 1313 之 1552 篇)：