描述
你需要去上n门九章的课才能获得offer,这些课被标号为 0 到 n-1 。
有一些课程需要“前置课程”,比如如果你要上课程0,你需要先学课程1,我们用一个匹配来表示他们: [0,1]
给你课程的总数量和一些前置课程的需求,返回你为了学完所有课程所安排的学习顺序。
可能会有多个正确的顺序,你只要返回一种就可以了。如果不可能完成所有课程,返回一个空数组。
样例
给定 n = 2, prerequisites = [[1,0]]
返回 [0,1]
给定 n = 4, prerequisites = [1,0],[2,0],[3,1],[3,2]]
返回 [0,1,2,3] or [0,2,1,3]
思路
拓扑排序的变形题,和课程表题类似,只是把结点输出而已
代码
public class Solution {
/**
* @param numCourses a total of n courses
* @param prerequisites a list of prerequisite pairs
* @return the course order
*/
public int[] findOrder(int numCourses, int[][] prerequisites) {
List[] edges = new ArrayList[numCourses];
int[] degree = new int[numCourses];
for (int i = 0;i < numCourses; i++)
// edges[i] 本身就是一个数组,即 edges 中的每个元素都是一个数组,edge 的初始化
edges[i] = new ArrayList<Integer>();
for (int i = 0; i < prerequisites.length; i++) {
// 统计学习某门课需要先修的课程数目,即入度
degree[prerequisites[i][0]] ++ ;
// 把某门课的后续课程全部加入到该课对应的 edges 数组中
edges[prerequisites[i][1]].add(prerequisites[i][0]);
}
Queue queue = new LinkedList();
for(int i = 0; i < degree.length; i++){
// 把先修课程数目为 0 的课程加入队列
if (degree[i] == 0) {
queue.add(i);
}
}
// count 表示处理课程数目
int count = 0;
int[] order = new int[numCourses];
while(!queue.isEmpty()){
// queue.poll() 抛出的是 Integer,要转化成整型
int course = (int)queue.poll();
// 按照队列的顺序把抛出的数值添加到 order 中去
order[count] = course;
count ++;
// 处理当前课程 course 的后续课程,edges[course] 是一个数组
int n = edges[course].size();
for(int i = n - 1; i >= 0 ; i--){
// 后续课程 point,edges 是用 ArrayList 生成的动态数组,用 get 来得到数组中的元素
int pointer = (int)edges[course].get(i);
// 每处理到一门课程,该课程的度都要 -1
degree[pointer]--;
// 把度为 0 的加入到队列,不是 0 的跳过
if (degree[pointer] == 0) {
queue.add(pointer);
}
}
}
// 检查
if (count == numCourses) {
return order;
}
// 异常情况返回空数组
return new int[0];
}
}