LEETCODE 210. Course Schedule II解题思路分析

题目大意：

课程表 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/