LeetCode 207. 课程表

题目描述这个学期需要选修numCourses门课程课程编号为0到numCourses - 1。数组prerequisites表示课程之间的先修关系其中prerequisites[i] [ai, bi]表示如果要学习课程ai必须先学习课程bi。例如[0, 1]表示想学习课程0需要先完成课程1。要求判断是否可以完成所有课程。如果可以返回true否则返回false。初始思路一开始想到的是把二维数组转成链表然后判断链表里是否存在循环。但这题不是普通链表问题。一个课程可能有多个后续课程也可能被多个课程依赖所以它本质上是一张有向图不是一条链表。如果课程之间存在环就说明有些课程互相依赖无法完成所有课程。例如0 - 1 1 - 0这就表示学习0之前要先学1学习1之前又要先学0形成了死循环。解题思路这题可以用 DFS 判断有向图中是否存在环。先根据prerequisites建图g[p[1]].add(p[0]);这里的方向是先修课 - 后续课也就是如果p [a, b]表示学a之前必须先学b所以建边b - a。然后用三色标记记录每个课程的访问状态0未访问。1正在访问。2已经访问完成。DFS 过程中如果遇到一个状态为1的节点说明这个节点还在当前递归路径上又被重新访问到了所以存在环。如果存在环就无法完成所有课程返回false。为什么需要三色标记这题不能只用一个简单的visited。因为有向图判环时需要区分两种状态这个点以前访问过并且已经确认它后面的路径没有环。这个点正在当前 DFS 路径中还没有退出递归。只有遇到“正在访问”的点才说明形成了环。也就是代码里的if (color[y] 1) { return true; }当一个节点的所有后续节点都 DFS 完成后要把它标记成2color[x] 2;表示这个点已经检查完成以后再遇到它就不用重复搜索。易错点1. 建图方向prerequisites[i] [ai, bi]的含义是学ai之前要先学bi。所以边的方向应该是bi - ai对应代码g[p[1]].add(p[0]);2. DFS 结束后要标记为完成如果一个点搜索完没有发现环要把它从1改成2。否则其他路径再次访问到它时可能会误以为遇到了环。3. 外层要遍历所有课程图不一定是连通的。有些课程可能和课程0完全不在一个连通块里所以不能只从一个课程开始 DFS而是要遍历所有课程for (int i 0; i numCourses; i) { if (color[i] 0 dfs(i, g, color)) { return false; } }代码实现class Solution { public boolean canFinish(int numCourses, int[][] prerequisites) { ListInteger[] g new ArrayList[numCourses]; Arrays.setAll(g, i - new ArrayList()); int[] color new int[numCourses]; for (int[] p : prerequisites) { g[p[1]].add(p[0]); } for (int i 0; i numCourses; i) { if (color[i] 0 dfs(i, g, color)) { return false; } } return true; } public boolean dfs(int x, ListInteger[] g, int[] color) { color[x] 1; for (int y : g[x]) { if (color[y] 1 || color[y] 0 dfs(y, g, color)) { return true; } } color[x] 2; return false; } }复杂度分析时间复杂度O(numCourses prerequisites.length)。每个课程节点和每条先修边最多被访问一次。空间复杂度O(numCourses prerequisites.length)。邻接表需要存储所有边递归栈和颜色数组最多需要O(numCourses)。复盘这题的关键是把课程关系看成一张有向图然后判断图里有没有环。最开始想用链表判环是因为抓住了“循环依赖”这个方向但没有意识到课程关系不是一条链而是可能一对多、多对一的图结构。下次遇到类似题时可以先检查三点依赖关系能不能抽象成有向图。边方向是否是先修课 - 后续课。DFS 判环时是否区分了未访问、正在访问、已完成三种状态。