溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這期內容當中小編將會給大家帶來有關golang中怎么利用leetcode實現課程表排序，文章內容豐富且以專業的角度為大家分析和敘述，閱讀完這篇文章希望大家可以有所收獲。
示例 1:
輸入: 2, [[1,0]]
輸出: [0,1]
解釋: 總共有 2 門課程。要學習課程 1，你需要先完成課程 0。因此，正確的課程順序為 [0,1] 。
示例 2:
輸入: 4, [[1,0],[2,0],[3,1],[3,2]]
輸出: [0,1,2,3] or [0,2,1,3]
解釋: 總共有 4 門課程。要學習課程 3，你應該先完成課程 1 和課程 2。并且課程 1 和課程 2 都應該排在課程 0 之后。
因此，一個正確的課程順序是 [0,1,2,3] 。另一個正確的排序是 [0,2,1,3] 。
說明:
輸入的先決條件是由邊緣列表表示的圖形，而不是鄰接矩陣。詳情請參見圖的表示法。
你可以假定輸入的先決條件中沒有重復的邊。
提示:
這個問題相當于查找一個循環是否存在于有向圖中。如果存在循環，則不存在拓撲排序，因此不可能選取所有課程進行學習。
通過 DFS 進行拓撲排序 - 一個關于Coursera的精彩視頻教程（21分鐘），介紹拓撲排序的基本概念。
拓撲排序也可以通過 BFS 完成。
解題思路：
1,對課程排序是，前一篇的遞進，有向圖的top排序，采用廣度優先搜索（BFS）
2，首先將邊緣列表轉化成逆鄰接矩陣，并記錄每個前綴課程的入度
3，入度為0 的課程沒有依賴，可以先上，放入隊列
4，一次從隊列中取節點
A，放入返回數據
B，將依賴此節點的所有鄰接節點的入度減一（刪除此節點后，鄰接節點的依賴減少）
C，將修正后入度為0 的節點放入隊列
D，循環直至隊列為空
4，返回數據如果長度等于課程長度，說明沒有環，否則有環
func findOrder(numCourses int, prerequisites [][]int) []int {inverse_adj:=make([][]int,numCourses)out_degree:=make([]int,numCourses) //入度for i:=0;i<len(prerequisites);i++{//將邊緣列表轉換成逆鄰接矩陣的形式out_degree[prerequisites[i][0]]++inverse_adj[prerequisites[i][1]]=append(inverse_adj[prerequisites[i][1]],prerequisites[i][0])}r:=BFS(inverse_adj,out_degree)if len(r)==numCourses{return r}return nil}func BFS(inverse_adj [][]int,out_degree []int)(r []int){var q queuefor i:=0;i<len(out_degree);i++{if out_degree[i]==0{//入度為0，可以作為終點q.push(i)}}for !q.empty(){top:=q.pop()r=append([]int{top},r...)for _,precursor:=range(inverse_adj[top]){//將當前節點移除，所有前驅節點的出度減1out_degree[precursor]--if out_degree[precursor]==0{q.push(precursor)}}}return r}type queue struct{data []int}func(q*queue)empty()bool{return len(q.data)==0}func(q*queue)push(i int){q.data=append(q.data,i)}func(q*queue)pop()int{r:=q.data[len(q.data)-1]q.data=q.data[:len(q.data)-1]return r}
上述就是小編為大家分享的golang中怎么利用leetcode實現課程表排序了，如果剛好有類似的疑惑，不妨參照上述分析進行理解。如果想知道更多相關知識，歡迎關注億速云行業資訊頻道。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
