前往
大廳
主題

LeetCode - 210. Course Schedule II 解題心得

Not In My Back Yard | 2022-06-15 12:00:18 | 巴幣 2 | 人氣 229

題目連結:


題目意譯:
現在你總共有 numCourses 堂課必須修,編號為 0 到 numCourses - 1。你被給定一個陣列 prerequisites,其中 prerequisites[i] = [ai, bi] 代表著如果你想要修課堂 ai,則你需要先修完課程 bi。

例如,數對 [0, 1],代表著在修課程 0 之前你需要先完成課程 1。

回傳為了修完所有課程所需要按照的修課順序。如果有多組合法的答案,則回傳任意一個。如果不可能完成所有課程的話,則回傳一個空陣列。

限制:
1 ≦ numCourses ≦ 2000
0 ≦ prerequisites.length ≦ numCourses × (numCourses - 1)
prerequisites[i].length == 2
0 ≦ ai, bi < numCourses
ai != bi
所有數對 [ai, bi] 皆相異。



範例測資:
範例 1:
輸入: numCourses = 2, prerequisites = [[1,0]]
輸出: [0,1]
解釋: 總共有 2 堂課要修。為了修得課程 1 你需要先修完課程 0。所以正確的順序是 [0,1]。

範例 2:
輸入: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
輸出: [0,2,1,3]
解釋: 總共有 4 堂課。為了修得課程 3 你需要先修完課程 1 和 2。而課程 1 和 2 都需要在修完課程 0 後才能去修。
所以其中一種正確的順序為 [0,1,2,3]。另一種順序為 [0,2,1,3]。

範例 3:
輸入: numCourses = 1, prerequisites = []
輸出: [0]


解題思維:
如果把擋修(即大意中的修課前置條件,也就是陣列 prerequisites)視為一張圖上的邊的話,則可以看到本題所求的一個「正確」的修課順序即是這張圖的一個拓樸排序(Topological Sort),作法如這題




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作