210. 課程表 II

題目描述：現(xiàn)在你總共有 numCourses 門課需要選，記為 0 到 numCourses - 1。給你一個(gè)數(shù)組 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在選修課程 ai 前 必須 先選修 bi 。

例如，想要學(xué)習(xí)課程 0 ，你需要先完成課程 1 ，我們用一個(gè)匹配來(lái)表示：[0,1] 。
返回你為了學(xué)完所有課程所安排的學(xué)習(xí)順序。可能會(huì)有多個(gè)正確的順序，你只要返回 任意一種 就可以了。如果不可能完成所有課程，返回 一個(gè)空數(shù)組 。

考察重點(diǎn)：DFS——深度優(yōu)先搜索

func dfs2(rec [][]int, lenRec []int, flag []int, res *[]int, nowNum int) bool { //思路與p207一致，加入15,16行記錄遍歷順序if flag[nowNum] == -1 {return false} else if flag[nowNum] == 1 {return true}flag[nowNum] = -1for i := 0; i < lenRec[nowNum]; i++ {if !dfs2(rec, lenRec, flag, res, rec[nowNum][i]) {return false}}t1 := *res //t1為地址res中的值 //如果dfs2()中的參數(shù)是res []int，則append之后返回的新數(shù)組與參數(shù)地址不同，則無(wú)法通過(guò)將res放在參數(shù)中來(lái)修改它*res = append(t1, nowNum) //所以這里存放的是res *[]int，將res修改完成后，把地址res下存放的值，替換為append返回值flag[nowNum] = 1return true } func FindOrder(numCourses int, prerequisites [][]int) []int {var rec [][]intfor i := 0; i < 10; i++ {t := make([]int, numCourses)rec = append(rec, t)}lenRec := make([]int, numCourses)flag := make([]int, numCourses)res := &[]int{}for i := 0; i < len(prerequisites); i++ {temp := prerequisites[i][0]rec[temp][lenRec[temp]] = prerequisites[i][1]lenRec[temp]++}for i := 0; i < numCourses; i++ {if flag[i] == 0 {if !dfs2(rec, lenRec, flag, res, i) {return []int{} //如果有環(huán)，返回空數(shù)組}}}return *res //返回地址res下存放的值 }

總結(jié)

以上是生活随笔為你收集整理的LeetCode—210. 课程表 II的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。