X

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/
Categories: leetcode
admin:

View Comments (0)