X

LEETCODE 207. Course Schedule解题思路分析

题目大意:

课程表

现在你总共有 n 门课需要选,记为 0 到 n-1。

在选修某些课程之前需要一些先修课程。 例如,想要学习课程 0 ,你需要先完成课程 1 ,我们用一个匹配来表示他们: [0,1]

给定课程总量以及它们的先决条件,判断是否可能完成所有课程的学习?

示例 1:

输入: 2, [[1,0]]
输出: true
解释: 总共有 2 门课程。学习课程 1 之前,你需要完成课程 0。所以这是可能的。
示例 2:

输入: 2, [[1,0],[0,1]]
输出: false
解释: 总共有 2 门课程。学习课程 1 之前,你需要先完成​课程 0;并且学习课程 0 之前,你还应先完成课程 1。这是不可能的。
说明:

输入的先决条件是由边缘列表表示的图形,而不是邻接矩阵。详情请参见图的表示法。
你可以假定输入的先决条件中没有重复的边。


如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=207

解题思路分析:

这是一道中等难度的题目。普通的dfs思路完全可以搞定。之所以此题要发博客分析一下,原因在于本题的dfs可以植入拓扑排序(Topological Sorting)的思想,来更加方便的解题。同时也为了本题目的续集-《课程表2》做准备。

续集文章看这里:LEETCODE 210. COURSE SCHEDULE II解题思路分析

先简单说下拓扑排序,拓扑排序通常用来“排序”具有依赖关系的任务。 比如本题的例子,如果想修课程1,就必须先修完课程0。故在这个课程任务中,任意两个课程要么具有确定的先后关系,要么是没有关系,绝对不存在互相矛盾的关系(即环路)。

因此,回到本题,对于是否能够完成所有课程的学习,也就是求所有课程是否能够满足拓扑排序。

实现拓扑排序的框架基本上是dfs深度优先搜索的写法,此外我们还需要引入一个visited[]数组,表示每一个节点的状态。其中visited[i]的值:

・ 0 代表还未访问的状态
・ 1 代表正在访问的状态
・ 2 代表已经访问完成

如果一个节点还未被访问过,则他是可以访问的,进而递归查看其后续节点(也就是本题中对应当前课程的所有先修课)。

如果当前访问节点的状态为1,说明该节点正在递归访问其后续节点,此时再次回到当前节点时,只能说明递归访问路径出现了环路(比如课程A的先修课是B,此时A的状态为1,递归到B时发现其先修课为A,再递归到A时发现其状态为1,这就是回路。),这是不能满足条件的情况,可以直接返回false。

如果状态为2,则说明当前节点的所有后续路径已经遍历(递归)完成,符合拓扑排序的条件,这时再访问到此节点,可以直接返回true。(比如我们知道课程A的先修课是B,而B没有先修课要求,这时A到B之间是满足条件的,因此A和B的状态都可以更新为2。接下来出现了一门课程C,其先修课为A,因为A的转态是2,所以我们可以清楚的直到A,B,C之间没有回路)

看下本题的完整代码:

public boolean canFinish(int numCourses, int[][] prerequisites) {
    // 为了将prerequisites转化为图结构,定义一个graph数组。
    // graph下标代表课程编号,值代表该课程所有先修课列表。
    List<Integer>[] graph = new ArrayList[numCourses];
    // 初始化graph
    for (int i = 0; i < numCourses; i++) {
        graph[i] = new ArrayList<>();
    }
    // 将prerequisites转化为图结构。
    for (int[] prerequisite : prerequisites) {
        graph[prerequisite[0]].add(prerequisite[1]);
    }
    // 创建一个visited 数组
    // 0: unvisited; 1: visiting 2: visited
    int[] visited = new int[numCourses];
    // 循环每一节课
    for (int i = 0; i < numCourses; i++) {
        // dfs递归该课的先修课路径上是否存在回路。
        if (!dfs(graph, i, visited)) {
            // 如果存在回路可直接返回false。
            return false;
        }
    }
    return true;
}
// 返回true代表没有回路,false代表发现回路 
private boolean dfs(List<Integer>[] graph, int currentCourse, int[] visited) {
    // visited状态为1表示发现回路,返回false
    if (visited[currentCourse] == 1) {
        return false;
    }
    // visited状态为2表示当前节点之后不存在回路,可直接返回true
    if (visited[currentCourse] == 2) {
        return true;
    }
    // 开始递归当前节点的先修课
    // 将状态更新为1
    visited[currentCourse] = 1;
    // 循环当前课的所有先修课
    for (int preCourse : graph[currentCourse]) {
        // 递归查看先修课之后的路径是否有回路
        if (!dfs(graph, preCourse, visited)) {
            // 如果有回路直接返回false。
            return false;
        }
    }
    // 当前节点的所有先修课路径循环结束后,将visited更新为2。
    visited[currentCourse] = 2;
    return true;
}

本解法执行时间为2ms

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: https://leetcode.jp/leetcode-207-course-schedule解题思路分析/
Categories: leetcode
admin:

View Comments (0)