207. 课程表中等提示你这个学期必须选修numCourses门课程记为0到numCourses - 1。在选修某些课程之前需要一些先修课程。 先修课程按数组prerequisites给出其中prerequisites[i] [ai, bi]表示如果要学习课程ai则必须先学习课程bi。例如先修课程对[0, 1]表示想要学习课程0你需要先完成课程1。请你判断是否可能完成所有课程的学习如果可以返回true否则返回false。示例 1输入numCourses 2, prerequisites [[1,0]] 输出true 解释总共有 2 门课程。学习课程 1 之前你需要完成课程 0 。这是可能的。示例 2输入numCourses 2, prerequisites [[1,0],[0,1]] 输出false 解释总共有 2 门课程。学习课程 1 之前你需要先完成课程 0 并且学习课程 0 之前你还应先完成课程 1 。这是不可能的。提示1 numCourses 20000 prerequisites.length 5000prerequisites[i].length 20 ai, bi numCoursesprerequisites[i]中的所有课程对互不相同 核心笔记课程表 (拓扑排序 / DFS 找环)1. 核心思想 (一句话总结)“红绿灯机制遇到‘黄灯’就是追尾环遇到‘红灯’就是安全。”我们需要区分三种状态防止重复计算并精准定位“回边”。0 (White/未访问)处女地没去过。1 (Gray/正在访问)当前递归栈中的节点黄灯。如果在递归中又遇到了 1说明咬到了自己的尾巴 - 有环2 (Black/已完成)死胡同或已经确认安全的节点红灯。下次遇到直接跳过不用再跑一遍。2. 算法流程 (三步走)建图 (Adjacency List)把[课程, 前置]转化为前置 - 课程的邻接表。遍历所有节点图可能不是连通的所以外层要用for循环遍历每一个节点。DFS (三色状态流转)进门标记为1(正在经手)。查邻居邻居是1报警有环邻居是0递归进去查。邻居是2安全的无视。出门标记为2(封存归档)表示从我出发的所有路都走通了且没环。 代码回忆清单 (带注释版)✅ 举例假设prerequisites [[1,0], [2,0], [3,1]]循环过程p [1, 0]→g[0].add(1)→g[0] [1]p [2, 0]→g[0].add(2)→g[0] [1, 2]p [3, 1]→g[1].add(3)→g[1] [3]最终邻接表g[0] [1, 2] // 学完 0 可以学 1 或 2 g[1] [3] // 学完 1 可以学 3 g[2] [] // 学完 2 没有后续课程 g[3] [] // 学完 3 没有后续课程// 题目LC 207. Course Schedule class Solution { public boolean canFinish(int numCourses, int[][] prerequisites) { // 1. 建图 (邻接表) //创建一个数组每个元素是一个列表 ListInteger[] g new ArrayList[numCourses]; //给每个位置初始化一个空列表 Arrays.setAll(g, i - new ArrayList()); for (int[] p : prerequisites) { // p[1] 是先修课p[0] 是后修课 // 边方向先修 - 后修 // 从先修课 p[1] 指向后修课 p[0] g[p[1]].add(p[0]); } // 2. 状态数组 (0:未访, 1:递归中, 2:已完成) int[] colors new int[numCourses]; // 3. 处理非连通图 (孤岛也要查) for (int i 0; i numCourses; i) { // 只有没访问过的才进 DFS // 如果 dfs 返回 true说明找到了环也就是无法完成 - return false if (colors[i] 0 dfs(i, g, colors)) { return false; } } return true; // 全跑完了没发现环 } // 返回值true 表示“发现了环” private boolean dfs(int x, ListInteger[] g, int[] colors) { colors[x] 1; // 标记我正在这条路径上 (入栈) // g[x] 是学完 x 后可以学的课程列表。 // y 就是其中一个后续课程。 for (int y : g[x]) { // 核心判断逻辑 if (colors[y] 1) { return true; // 撞见自己人/祖先了 - 环 } if (colors[y] 0 dfs(y, g, colors)) { return true; // 递归子节点发现了环层层上报 } // colors[y] 2 的情况直接跳过 (剪枝) } colors[x] 2; // 标记我和我的子孙都检查过了没问题 (出栈) return false; // 平安无事 } }⚡ 快速复习 CheckList (易错点)[ ]为什么不能只用 boolean visited普通的visited只能分“去过”和“没去过”。我们需要区分是“当前递归路径里遇到过 (环)”还是“别的路径已经验证过是安全的 (剪枝)”。这就是状态1和2的区别。[ ]返回值逻辑绕晕了dfs返回true有坏人 (有环)。主函数if (dfs(...))成立说明有环课程表没法修完所以主函数返回false。负负得正的逻辑要理清。[ ]边的方向通常题目给[A, B]表示修 A 必须先修 B。建图最好是B - A(学了 B 才能学 A)。这样如果有环逻辑依然成立。️ 数字演练假设依赖0 - 11 - 0(互为前置死循环)。DFS(0)Colors[0] 1。看邻居1。1是颜色0- 递归DFS(1)。DFS(1)Colors[1] 1。看邻居0。关键点0的颜色是1(说明 0 还在递归栈里还没有变绿)。Return True(发现环)。Back to DFS(0)收到子递归的True。Return True。Main收到True(有环)。Return False(不能完成)。