資訊專欄INFORMATION COLUMN
Problem
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, return the ordering of courses you should take to finish all courses.
There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.
Example 1:
Input: 2, [[1,0]] Output: [0,1]
Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1] .
Example 2:
Input: 4, [[1,0],[2,0],[3,1],[3,2]] Output: [0,1,2,3] or [0,2,1,3]
Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3] .
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.
class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
int[] degree = new int[numCourses];
Map> map = new HashMap<>();
for (int[] pair: prerequisites) {
int parent = pair[1], child = pair[0];
if (!map.containsKey(parent)) {
List list = new ArrayList<>();
list.add(child);
map.put(parent, list);
} else map.get(parent).add(child);
degree[child]++;
}
Queue queue = new LinkedList<>();
for (int i = 0; i < degree.length; i++) {
if (degree[i] == 0) queue.offer(i);
}
int[] res = new int[numCourses];
int k = 0;
while (!queue.isEmpty()) {
int parent = queue.poll();
res[k++] = parent;
if (map.containsKey(parent)) {
for (int child: map.get(parent)) {
degree[child]--;
if (degree[child] == 0) queue.offer(child);
}
}
}
if (k != numCourses) return new int[0];
return res;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/77201.html
摘要：建立入度組成，把原來輸入的無規(guī)律，轉(zhuǎn)換成另一種表示圖的方法。找到為零的點(diǎn)，放到里，也就是我們圖的入口。對(duì)于它的也就是指向的。如果這些的入度也變成，也就變成了新的入口，加入到里，重復(fù)返回結(jié)果。這里題目有可能沒有預(yù)修課，可以直接上任意課程。 Some courses may have prerequisites, for example to take course 0 you have ...
Problem 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 a...
Course Schedule I 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 e...
Course Schedule Problem 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, whi...
Problem 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 ...
閱讀 3579·2023-04-25 20:41
閱讀 2674·2023-04-25 16:40
閱讀 1444·2021-09-23 11:44
閱讀 1262·2021-09-10 10:51
閱讀 1691·2021-09-07 09:59
閱讀 1679·2019-12-27 12:08
閱讀 567·2019-08-30 15:44
閱讀 3344·2019-08-30 11:08
