本文最后更新于 390 天前,其中的信息可能已经有所发展或是发生改变。
题目描述:
你这个学期必须选修 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]
中的所有课程对 互不相同
解法一:拓扑排序
算法思路:
题意理解:
- 一共有
n
门课要上,编号为0 ~ n-1
。 - 先决条件
[1, 0]
,表示要上课1
,必须先上完课0
。 - 给你
n
和一个先决条件表,请你分析是否能完成所有课程。
举例分析:
假设有 n = 6
,先决条件表:[[3, 0], [3, 1], [4, 1], [4, 2], [5, 3], [5, 4]]
我们可以用有向图来表示课程之间的依赖关系:
上图叫有向无环图,把一个 有向无环图 转变成 线性的排序 叫做拓扑排序。
- 初始时,课程 0、1、2 没有前置课程,节点的入度为 0,课程 3、4、5 分别有两门前置课程,节点入度为 2。
- 每次选择课程时,只能选择没有前置课程的,也就是入度为
0
的。 - 在上面的例子中:
- 先选择 0,课 3 的前置课程少了一门,入度由 2 变成 1。
- 接着选 1,课 3 的入度变为 0,课 4 的入度变为 1。
- 接着选 2,课 4 的入度变为 0。
- 接着可以依次选择课 3 和课 4,直到选择不到入度为 0 的课程为止。
- 当选择不到入度为0的课程后,如果还有课程入度不为 0,那么不能完成所有的课程,反之,则可以学完所有课程。
代码实现:
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
int[] inDegree = new int[numCourses]; // 入度数组
HashMap<Integer, List<Integer>> map = new HashMap<>(); // 邻接表
// 构建入度数组和邻接表
for (int i = 0; i < prerequisites.length; i++) {
inDegree[prerequisites[i][0]]++; // 求课的初始入度值
if (map.containsKey(prerequisites[i][1])) { // 当前课已经存在于邻接表
map.get(prerequisites[i][1]).add(prerequisites[i][0]); // 添加依赖它的后续课
} else { // 当前课不存在于邻接表
List<Integer> list = new ArrayList<>();
list.add(prerequisites[i][0]);
map.put(prerequisites[i][1], list);
}
}
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < inDegree.length; i++) { // 所有入度为0的课入列
if (inDegree[i] == 0) {
queue.offer(i);
}
}
while (!queue.isEmpty()) {
int selected = queue.poll(); // 当前选的课,出列
List<Integer> toEnQueue = map.get(selected); // 获取这门课对应的后续课
if (toEnQueue != null && !toEnQueue.isEmpty()) { // 确实有后续课
for (int i = 0; i < toEnQueue.size(); i++) {
int dependentCourse = toEnQueue.get(i);
inDegree[dependentCourse]--; // 依赖它的后续课的入度-1
if (inDegree[dependentCourse] == 0) { // 如果因此减为0,入列
queue.offer(dependentCourse);
}
}
}
}
return count == numCourses; // 选了的课等于总课数,true,否则false
}
}
复杂度分析:
时间复杂度: O(n + m)
空间复杂度: O(n + m)