你这个学期必须选修 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]
中的所有课程对 互不相同
TODO: 研究一下图相关算法和拓扑排序。
拓扑排序通常用来“排序”具有依赖关系的任务。
拓扑排序出来的结果是应该不是有序(升序或降序)。只是一个前后顺序。
- 一刷
-
link:{sourcedir}/_0207_CourseSchedule.java[role=include]
- 二刷
-
link:{sourcedir}/_0207_CourseSchedule_2.java[role=include]
- 三刷
-
link:{sourcedir}/_0207_CourseSchedule_3.java[role=include]
思考题:参考资料中提到,表示图可以使用"邻接矩阵"和"邻接表"。尝试使用邻接表来重新实现。