溫馨提示×

溫馨提示×

您好,登錄后才能下訂單哦!

密碼登錄×
登錄注冊×
其他方式登錄
點擊 登錄注冊 即表示同意《億速云用戶服務(wù)條款》

golang中怎么利用leetcode實現(xiàn)課程表排序

發(fā)布時間:2021-08-12 14:44:55 來源:億速云 閱讀:145 作者:Leah 欄目:大數(shù)據(jù)

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

示例 1:

輸入: 2, [[1,0]] 

輸出: [0,1]

解釋: 總共有 2 門課程。要學(xué)習(xí)課程 1,你需要先完成課程 0。因此,正確的課程順序為 [0,1] 。

示例 2:

輸入: 4, [[1,0],[2,0],[3,1],[3,2]]

輸出: [0,1,2,3] or [0,2,1,3]

解釋: 總共有 4 門課程。要學(xué)習(xí)課程 3,你應(yīng)該先完成課程 1 和課程 2。并且課程 1 和課程 2 都應(yīng)該排在課程 0 之后。

     因此,一個正確的課程順序是 [0,1,2,3] 。另一個正確的排序是 [0,2,1,3] 。

說明:

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

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

提示:

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

通過 DFS 進行拓撲排序 - 一個關(guān)于Coursera的精彩視頻教程(21分鐘),介紹拓撲排序的基本概念。

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

解題思路:

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

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

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<len(prerequisites);i++{        //將邊緣列表轉(zhuǎn)換成逆鄰接矩陣的形式        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<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]){            //將當(dāng)前節(jié)點移除,所有前驅(qū)節(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)課程表排序了,如果剛好有類似的疑惑,不妨參照上述分析進行理解。如果想知道更多相關(guān)知識,歡迎關(guān)注億速云行業(yè)資訊頻道。

向AI問一下細節(jié)

免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。

AI