题目大意：
课程表 II
现在你总共有 n 门课需要选，记为 0 到 n-1。
在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]
给定课程总量以及它们的先决条件，返回你为了学完所有课程所安排的学习顺序。
可能会有多个正确的顺序，你只要返回一种就可以了。如果不可能完成所有课程，返回一个空数组。
示例 1:
输入: 2, [[1,0]]
输出: [0,1]
解释: 总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。
示例 2:
输入: 4, [[1,0],[2,0],[3,1],[3,2]]
输出: [0,1,2,3] or [0,2,1,3]
解释: 总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。
说明:
输入的先决条件是由边缘列表表示的图形，而不是邻接矩阵。详情请参见图的表示法。
你可以假定输入的先决条件中没有重复的边。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=210
解题思路分析：
本题是 LEETCODE 207. COURSE SCHEDULE解题思路分析 的续集，如果没有看过之前的文章，强烈建议首先做一下207这题，由于上一篇文章已经讲得非常详细，这里就不再啰嗦。本题解法与课程表1的思路完全一致，用到了dfs以及拓扑排序，唯一的不同是这里要求返回一组可能的排序方案。按照之前的思路，我们还是要判断出课程是否能够产生合理的排序，如果可能，我们需要在判断完每一个节点后（将visited更新为2的时间点）将其加入到返回list中即可。
看下完整代码。（本题代码就不做注释了，如有不懂可以参照LEETCODE 207. COURSE SCHEDULE解题思路分析）
public int[] findOrder(int numCourses, int[][] prerequisites) {
List<Integer>[] graph = new ArrayList[numCourses];
for (int i = 0; i < numCourses; i++) {
graph[i] = new ArrayList<>();
}
for (int[] prerequisite : prerequisites) {
graph[prerequisite[0]].add(prerequisite[1]);
}
// 0: unvisited; 1: visiting 2: visited
int[] visited = new int[numCourses];
List<Integer> tempRes = new ArrayList<>();
for (int i = 0; i < numCourses; i++) {
if (!dfs(graph, i, visited, tempRes)) {
return new int[0];
}
}
int[] res = new int[numCourses];
for (int i = 0; i < numCourses; i++) {
res[i] = tempRes.get(i);
}
return res;
}
private boolean dfs(List<Integer>[] graph, int currentCourse, int[] visited, List<Integer> temp) {
if (visited[currentCourse] == 1) {
return false;
}
if (visited[currentCourse] == 2) {
return true;
}
visited[currentCourse] = 1;
for (int preCourse : graph[currentCourse]) {
if (!dfs(graph, preCourse, visited, temp)) {
return false;
}
}
visited[currentCourse] = 2;
temp.add(currentCourse);
return true;
} 本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-210-course-schedule-ii/
View Comments (0)