Re: [閒聊] 每日leetcode

[JIWP (神楽めあ的錢包)]

2097. Valid Arrangement of Pairs

思路:

用有向圖去解

先找start的那個點

如果有一個點的indegree-outdegree是-1，那他就是start

注意不一定會有這樣的點

如果每個點的outdegree-indegree都是0，那就隨便找個點當start

用path紀錄每個邊 path[i]為第i點可進入的其他點

從start開始dfs

從start開始走，走過的點要從path中移除

當有一個點j其path[j]沒有東西的話，他就是當前的最後一個點

就這樣一直找最後一個點

最後反過來組合成題目所需就好

golang code :

func validArrangement(pairs [][]int) [][]int {
        indegree, path, ans := make(map[int]int), make(map[int][]int), make([][]int,
len(pairs))
        start, idx := pairs[0][0], len(pairs)-1
        for _, val := range pairs {
                indegree[val[1]]++
                indegree[val[0]]--
                path[val[0]] = append(path[val[0]], val[1])
        }
        for key, val := range indegree {
                if val == -1 {
                        start = key
                }
        }
        var dfs func(int)
        dfs = func(node int) {
                for len(path[node]) > 0 {
                        nextnode := path[node][0]
                        path[node] = path[node][1:]
                        dfs(nextnode)
                        ans[idx] = []int{node, nextnode}
                        idx--
                }
        }
        dfs(start)
        return ans
}

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.72.231.18 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1733146774.A.E7D.html
推 Furina: 大師
推 oin1104: 大師 教我寫程式