這期內(nèi)容當中小編將會給大家?guī)碛嘘Pgolang中怎么利用leetcode實現(xiàn)課程表排序，文章內(nèi)容豐富且以專業(yè)的角度為大家分析和敘述，閱讀完這篇文章希望大家可以有所收獲。

創(chuàng)新互聯(lián)建站為您提適合企業(yè)的網(wǎng)站設計?讓您的網(wǎng)站在搜索引擎具有高度排名，讓您的網(wǎng)站具備超強的網(wǎng)絡競爭力！結合企業(yè)自身，進行網(wǎng)站設計及把握，最后結合企業(yè)文化和具體宗旨等，才能創(chuàng)作出一份性化解決方案。從網(wǎng)站策劃到網(wǎng)站設計制作、成都網(wǎng)站設計， 我們的網(wǎng)頁設計師為您提供的解決方案。

示例 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] 。

說明:

輸入的先決條件是由邊緣列表表示的圖形，而不是鄰接矩陣。詳情請參見圖的表示法。

你可以假定輸入的先決條件中沒有重復的邊。

提示:

這個問題相當于查找一個循環(huán)是否存在于有向圖中。如果存在循環(huán)，則不存在拓撲排序，因此不可能選取所有課程進行學習。

通過 DFS 進行拓撲排序 - 一個關于Coursera的精彩視頻教程（21分鐘），介紹拓撲排序的基本概念。

拓撲排序也可以通過 BFS 完成。

解題思路：

1,對課程排序是，前一篇的遞進，有向圖的top排序，采用廣度優(yōu)先搜索（BFS）

2，首先將邊緣列表轉化成逆鄰接矩陣，并記錄每個前綴課程的入度

3，入度為0 的課程沒有依賴，可以先上，放入隊列

4，一次從隊列中取節(jié)點

A，放入返回數(shù)據(jù)

B，將依賴此節(jié)點的所有鄰接節(jié)點的入度減一（刪除此節(jié)點后，鄰接節(jié)點的依賴減少）

C，將修正后入度為0 的節(jié)點放入隊列

D，循環(huán)直至隊列為空

4，返回數(shù)據(jù)如果長度等于課程長度，說明沒有環(huán)，否則有環(huán)

func findOrder(numCourses int, prerequisites [][]int) []int {    inverse_adj:=make([][]int,numCourses)    out_degree:=make([]int,numCourses) //入度    for i:=0;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 queue    for i:=0;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]){            //將當前節(jié)點移除，所有前驅節(jié)點的出度減1            out_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實現(xiàn)課程表排序了，如果剛好有類似的疑惑，不妨參照上述分析進行理解。如果想知道更多相關知識，歡迎關注創(chuàng)新互聯(lián)行業(yè)資訊頻道。