友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
207. Course Schedule
There are a total of n courses you have to take, labeled from 0 to n-1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
Example 1:
Input: 2, [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0. So it is possible.Example 2:
Input: 2, [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0, and to take course 0 you should
also have finished course 1. So it is impossible.Note:
-
The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
-
You may assume that there are no duplicate edges in the input prerequisites.
思路分析
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;
}
思考题：参考资料中提到，表示图可以使用"邻接矩阵"和"邻接表"。尝试使用邻接表来重新实现。