資訊專欄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.
ExampleGiven n = 2, prerequisites = [[1,0]]
Return [0,1]
Given n = 4, prerequisites = [1,0],[2,0],[3,1],[3,2]]
Return [0,1,2,3] or [0,2,1,3]
public class Solution {
/*
* @param n: a total of n courses
* @param pre: a list of prerequisite pairs
* @return: the course order
*/
public int[] findOrder(int n, int[][] pre) {
// write your code here
ArrayList[] graph = new ArrayList[n];
for (int i = 0; i < n; i++) {
graph[i] = new ArrayList();
}
int[] indegree = new int[n];
for (int i = 0; i < pre.length; i++) {
graph[pre[i][1]].add(pre[i][0]);
indegree[pre[i][0]]++;
}
Queue queue = new LinkedList();
for (int i = 0; i < n; i++) {
if (indegree[i] == 0) queue.add(i);
}
int[] result = new int[n];
int index = 0;
while (!queue.isEmpty()) {
int node = queue.poll();
result[index++] = node;
ArrayList list = graph[node];
for (int i = 0; i < list.size(); i++) {
int cur = list.get(i);
indegree[cur]--;
if (indegree[cur] == 0) queue.add(cur);
}
}
return index == n ? result : new int[0];
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/69467.html
摘要：建立入度組成，把原來輸入的無規(guī)律，轉(zhuǎn)換成另一種表示圖的方法。找到為零的點，放到里，也就是我們圖的入口。對于它的也就是指向的。如果這些的入度也變成，也就變成了新的入口，加入到里，重復(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 as...
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...
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...
摘要：兩個循環(huán)遍歷整個矩陣，出現(xiàn)則將其周圍相鄰的全部標(biāo)記為，用子函數(shù)遞歸標(biāo)記。注意里每次遞歸都要判斷邊界。寫一個的，寫熟練。 Number of Islands Problem Given a boolean/char 2D matrix, find the number of islands. 0 is represented as the sea, 1 is represented as...
閱讀 1226·2023-04-26 02:20
閱讀 3349·2021-11-22 14:45
閱讀 4166·2021-11-17 09:33
閱讀 1020·2021-09-06 15:00
閱讀 1492·2021-09-03 10:30
閱讀 3900·2021-07-26 22:01
閱讀 1004·2019-08-30 15:54
閱讀 544·2019-08-30 15:43
