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 判环时是否区分了未访问、正在访问、已完成三种状态。

LeetCode 207. 课程表

相关推荐

浏览器又没网了？微信正常但网页打不开，我的修复踩坑记录

“智能”还是“智障”？——拆解AI报表生成器底层推理链的4个黑箱陷阱（含LLM+OLAP联合调试日志）

为什么你的 WordPress 后台总有一堆英文？聊聊“原生中文主题”与“汉化版”的坑

更多资讯

中专财务突破薪资瓶颈：从Excel到SQL的数据分析进阶路线

模型优化器实战：从800ms到170ms的推理加速与精度平衡

ESP32开发怎么选？Arduino、ESP-IDF、MicroPython对比与选型指南

CLI-Anything：声明式 CLI 运行时基础设施

CLI-Anything：面向智能体的可插拔CLI能力中枢

高维空间百年直觉被推翻：超立方体密铺反例的计算机搜索之路

今日更新

济南做网站多少钱：3个案例拆解，防黑源码下载全攻略

婚恋网站实战案例：避开3个高价坑，省钱50%还能跑赢流量

制作网页比较方便的软件怎么选?一文搞懂避坑指南

本周精选

如何彻底离线使用 Laya-CoreML：Hugging Face 下载、缓存机制与 local_files_only 详解

基于1Panel 部署MySQL MCP 服务：TaoToken 统一 Key 接入与 config.toml 配置实战

崇州园区营销网站建设避坑指南：5大注意事项保备案安全

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？