1. 题目描述
你这个学期必须选修 numCourses
门课程,记为 0
到 numCourses - 1
。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites
给出,其中 prerequisites[i] = [ai, bi]
,表示如果要学习课程 ai
则 必须 先学习课程 bi
。
例如,先修课程对
[0, 1]
表示:想要学习课程0
,你需要先完成课程1
。
请你判断是否可能完成所有课程的学习?如果可以,返回 true
;否则,返回 false
。
示例 1:
输入:numCourses = 2, prerequisites = [[1,0]]
输出:true
解释:总共有 2 门课程。学习课程 1 之前,你需要完成课程 0 。这是可能的。
示例 2:
输入:numCourses = 2, prerequisites = [[1,0],[0,1]]
输出:false
解释:总共有 2 门课程。学习课程 1 之前,你需要先完成课程 0 ;并且学习课程 0 之前,你还应先完成课程 1 。这是不可能的。
提示:
1 <= numCourses <= 2000
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
0 <= ai, bi < numCourses
prerequisites[i] 中的所有课程对 互不相同
2. 分析
核心思路:建图,广度优先搜索
1. 建图,维护节点入度
2. 广搜,从节点入度为0的课程(没有前置依赖)开始搜索,并更新其依赖的下游节点入度,将新的入度为0节点继续搜索,反复
3. 结果:无法再继续搜索时,返回搜索的课程数是否等于numCources
3. 代码
func canFinish(numCourses int, prerequisites [][]int) bool {
/*
1. 建图
a. degree[i] 表示节点i的入度
b. to[i][] 表示i的后置依赖
*/
degrees := make([]int, numCourses)
to := make([][]int, numCourses)
for _, prerequisted := range prerequisites {
// 学习a之前需要学习b a的前置依赖是b b->a
a, b := prerequisted[0], prerequisted[1]
// 更新b的依赖节点
to[b] = append(to[b], a)
// 更新a的入度
degrees[a]++
}
// 2. 从入度为0的节点开始,广度搜索,并统计搜索数
q := list.New()
for node, degree := range degrees {
if degree == 0 {
q.PushBack(node)
}
}
visited := 0
for q.Len() > 0 {
visited++
node := q.Remove(q.Front()).(int)
for _, target := range to[node] {
// 减少访问,更新入度
degrees[target]--
if degrees[target] == 0 {
q.PushBack(target)
}
}
}
// 3. 返回是否访问完所有节点
return visited == numCourses
}
评论