2021-10-27：课程表。你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。力扣207。
福大大 答案2021-10-27：
拓扑排序。
代码用golang编写。代码如下：
package main
import "fmt"
func main() {
numCourses := 2
prerequisites := [][]int{{1, 0}}
ret := canFinish1(numCourses, prerequisites)
fmt.Println(ret)
}
// 一个node，就是一个课程
// name是课程的编号
// in是课程的入度
type Course struct {
name int
in int
nexts []*Course
}
func NewCourse(n int) (res *Course) {
res = &Course{}
res.name = n
res.in = 0
res.nexts = make([]*Course, 0)
return
}
func canFinish1(numCourses int, prerequisites [][]int) bool {
if len(prerequisites) == 0 {
return true
}
// 一个编号 对应 一个课的实例
nodes := make(map[int]*Course)
for _, arr := range prerequisites {
to := arr[0]
from := arr[1] // from -> to
if _, ok := nodes[to]; !ok {
nodes[to] = NewCourse(to)
}
if _, ok := nodes[from]; !ok {
nodes[from] = NewCourse(from)
}
t := nodes[to]
f := nodes[from]
f.nexts = append(f.nexts, t)
t.in++
}
needPrerequisiteNums := len(nodes)
//Queue<Course> zeroInQueue = new LinkedList<>();
zeroInQueue := make([]*Course, 0)
for _, node := range nodes {
if node.in == 0 {
zeroInQueue = append(zeroInQueue, node)
}
}
count := 0
for len(zeroInQueue) > 0 {
//Course cur = zeroInQueue.poll();
cur := zeroInQueue[len(zeroInQueue)-1]
zeroInQueue = zeroInQueue[0 : len(zeroInQueue)-1]
count++
for _, next := range cur.nexts {
next.in--
if next.in == 0 {
zeroInQueue = append(zeroInQueue, next)
}
}
}
return count == needPrerequisiteNums
}
执行结果如下：
左神java代码
