LeetCode Notes#210_课程表II
LeetCodeContents
题目
解答
这一题其实就是#207 课程表的升级版，区别在于：
- 课程表一题只需要返回一个boolean变量，表示这组课程能否被修完；
- 本题需要给出这组课程正确的修读顺序。
方法1:BFS+队列
模拟拓扑排序的过程，参见什么是拓扑排序（Topological Sorting）。
class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
int[] res = new int[numCourses];
int index = 0;
//每个节点的入度
int[] inDegrees = new int[numCourses];
//每个节点指向的节点（后续课程）
List<List<Integer>> adjacency = new ArrayList<>();
//队列用于BFS
Queue<Integer> queue = new LinkedList<>();
//根据prerequisites填充inDegrees和adjacency
//adjacency的元素是ArrayList,需要进行初始化
for(int i = 0; i < numCourses; i++)
adjacency.add(new ArrayList<>());
//填充inDegrees和adjacency
for(int[] cp: prerequisites){
inDegrees[cp[0]]++;
adjacency.get(cp[1]).add(cp[0]);
}
//初始化队列，将所有入度为0的节点入队
for(int i = 0; i < numCourses; i++){
if(inDegrees[i] == 0) queue.offer(i);
}
//BFS过程：1. 队列里的课程可修，直接删除 2. 修完一些课程，它的邻居课程可能也可以修了，继续入队
while(!queue.isEmpty()){
int pre = queue.poll();
res[index++] = pre;
numCourses--;
for(Integer cur: adjacency.get(pre)){
if(--inDegrees[cur] == 0) queue.offer(cur);
}
}
if(numCourses == 0) return res;
return new int[0];
}
}复杂度分析
时间复杂度：O(n+m),n为课程数（图的节点数），m为先修课程要求数（图的边个数）
空间复杂度：O(n+m)，需要先将图存储为邻接表形式（即adjacency形式），他的大小就是n+m。至于其他的辅助变量queue,inDegrees空间都是n。
方法2:DFS+栈
class Solution {
List<List<Integer>> edges;
int[] visited;
int[] result;
boolean valid = true;
int index;
public int[] findOrder(int numCourses, int[][] prerequisites){
//edges其实就是在统计每个课程的后续课程，edges.get(i)就是一个i课程后续课程的列表
edges = new ArrayList<List<Integer>>();
//edges的元素是ArrayList,需要先进行一个初始化
for(int i = 0; i < numCourses; i++){
edges.add(new ArrayList<Integer>());
}
//visited维护了一个dfs访问的状态：0->未访问 1->已访问但是未入栈 2->已访问且已经入栈
visited = new int[numCourses];
//result用来模拟栈，即：从后向前填充数组
result = new int[numCourses];
//index初始化为最后一个下标，这样才可以从后向前填充数组
index = numCourses - 1;
//填充edges数组，即统计每个课程的后续课程，用于后续的dfs搜索
for(int[] info: prerequisites){
edges.get(info[1]).add(info[0]);
}
//对每一个课程进行dfs搜索，如果在某个课程的dfs课程中，已经遇到了环，可以直接跳出for循环过程
for(int i = 0; i < numCourses && valid; i++){
if(visited[i] == 0) dfs(i);
}
//根据valid变量决定返回值，如果valid == false说明这些课程不可能修完，直接返回空数组
if(!valid) return new int[0];
//否则就返回result数组，记录了正确的完成课程的顺序
return result;
}
//为什么这里的递归没有出口条件？其实出口条件有两个：1. edges.get(u)全都遍历了一遍，就可以返回了 2. 中途遇到了valid == false的情况，就不会把edges.get(i)遍历一遍，而是提前返回
public void dfs(int u){
//访问到一个课程，首先修改visit标记，表示当前课程正在被访问，但是还没有入栈（因为这还不是最后一个课程，需要进一步进行dfs)
visited[u] = 1;
//对当前课程的所有后续课程进行dfs(类似对树的左右子树进行dfs)
for(int v: edges.get(u)){
if(visited[v] == 0){
//dfs的主要目的就是判断是否有环（或者说维护valid变量）
dfs(v);
if(!valid) return;
}else if(visited[v] == 1){
//遇到了之前标记过的课程，就说明出现了环，修改valid变量为false,直接结束一切过程，返回空数组
valid = false;
return;
}
}
//课程入栈
visited[u] = 2;
result[index--] = u;
}
}复杂度分析
时间复杂度：O(n+m),n为课程数（图的节点数），m为先修课程要求数（图的边个数）
空间复杂度：O(n+m)，需要先将图存储为邻接表形式（即edges形式），他的大小就是n+m。至于其他的辅助变量result,visited空间都是n。递归调用的栈深度最高不会超过n(高度为n的情况下，图退化成为一个链表)。