友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
207. 课程表
你这个学期必须选修 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: 研究一下图相关算法和拓扑排序。
拓扑排序通常用来“排序”具有依赖关系的任务。
拓扑排序出来的结果是应该不是有序（升序或降序）。只是一个前后顺序。
-
一刷
-
二刷
-
三刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
* Runtime: 20 ms, faster than 36.81% of Java online submissions for Course Schedule.
*
* Memory Usage: 74.1 MB, less than 5.39% of Java online submissions for Course Schedule.
*
* Copy from: https://leetcode.com/problems/course-schedule/discuss/58516/Easy-BFS-Topological-sort-Java[Easy BFS Topological sort, Java - LeetCode Discuss]
*
* @author D瓜哥 · https://www.diguage.com
* @since 2020-01-26 16:36
*/
public boolean canFinish(int numCourses, int[][] prerequisites) {
int[][] matrix = new int[numCourses][numCourses];
int[] indegree = new int[numCourses];
for (int[] prere : prerequisites) {
int latter = prere[0];
int formmer = prere[1];
matrix[formmer][latter]++;
indegree[latter]++;
}
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < numCourses; i++) {
if (indegree[i] == 0) {
queue.offer(i);
}
}
int count = 0;
while (!queue.isEmpty()) {
Integer course = queue.poll();
count++;
for (int i = 0; i < numCourses; i++) {
if (matrix[course][i] != 0) {
if (--indegree[i] == 0) {
queue.offer(i);
}
}
}
}
return count == numCourses;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2020-01-26 16:36
*/
public boolean canFinish(int numCourses, int[][] prerequisites) {
int[] indegrees = new int[numCourses];
Map<Integer, List<Integer>> graph = new HashMap<>();
for (int[] pres : prerequisites) {
int pre = pres[1];
int post = pres[0];
indegrees[post]++;
List<Integer> posts = graph.getOrDefault(pre, new ArrayList<>());
posts.add(post);
graph.put(pre, posts);
}
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < numCourses; i++) {
if (indegrees[i] == 0) {
queue.offer(i);
}
}
int cnt = 0;
while (!queue.isEmpty()) {
int course = queue.poll();
cnt++;
for (int c : graph.getOrDefault(course, Collections.emptyList())) {
indegrees[c]--;
if (indegrees[c] == 0) {
queue.offer(c);
}
}
}
return cnt == numCourses;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-04-04 09:09:52
*/
public boolean canFinish(int numCourses, int[][] prerequisites) {
Map<Integer, List<Integer>> graph = new HashMap<>();
int[] indegree = new int[numCourses];
for (int[] p : prerequisites) {
List<Integer> children = graph.computeIfAbsent(p[0], k -> new ArrayList<>());
children.add(p[1]);
indegree[p[1]]++;
}
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < indegree.length; i++) {
if (indegree[i] == 0) {
queue.offer(i);
}
}
int cnt = 0;
while (!queue.isEmpty()) {
Integer c = queue.poll();
cnt++;
List<Integer> children = graph.getOrDefault(c, Collections.emptyList());
for (Integer child : children) {
indegree[child]--;
if (indegree[child] == 0) {
queue.offer(child);
}
}
}
return cnt == numCourses;
}
思考题：参考资料中提到，表示图可以使用"邻接矩阵"和"邻接表"。尝试使用邻接表来重新实现。