尧图网络 高端网站定制 · 原创设计
免费咨询热线
400-888-6620
免费获取方案
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 判环时是否区分了未访问、正在访问、已完成三种状态。
RELATED

相关推荐

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

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

🎉🎉🎉耶耶耶,今天终于解决了这个困扰我很久的问题!必须记录下来,帮到下一个被这个 bug 折磨的人。💻适用场景:右下角网络图标明明显示“已连接”,微信、QQ 都能正常聊天…

📅 2026/9/28 7:01:46
“智能”还是“智障”?——拆解AI报表生成器底层推理链的4个黑箱陷阱(含LLM+OLAP联合调试日志)

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

更多请点击: https://codechina.net 第一章:AI 自动生成报表 AI 自动生成报表正逐步取代传统手工编制与脚本驱动的报表流程,通过自然语言理解、结构化数据解析和模板化渲染能力,实现从原始数据到可交付业务文档的端到端自动化。该…

📅 2026/9/28 7:00:50
为什么你的 WordPress 后台总有一堆英文?聊聊“原生中文主题”与“汉化版”的坑

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

很多刚接触 WordPress 的朋友都会遇到一个尴尬的情况:在各大市场精心挑选了一个颜值在线的主题,安装激活后,前台看着挺美,一进后台——傻眼了,满屏的英文选项,或者更糟的是,一半中文一半英文的“…

📅 2026/9/28 7:28:38
MORE NEWS

更多资讯

📰

电工证如何查询信息良心建议:实操考试心里没底怕挂科

电工证如何查询信息良心建议:实操考试心里没底怕挂科 实操考试心里没底怕挂科?你不是一个人。尤其是像我这样在洛阳涧西区做项目现场管理员的,每天面对的都是实操和理论并重的考试流程,很多人一到考前就紧张得不行,怕电工证查不到信息、怕考不过、怕证书…

📰

重庆能考电工证吗怎么报名 电工证过期了怎么复审

重庆能考电工证吗怎么报名 电工证过期了怎么复审 证书过期了不知道怎么复审延期?你不是一个人。现在越来越多的特种作业人员,尤其是电工证持有者,面临证书到期后不知如何处理的问题。尤其是在重庆,很多人问:“ 重庆能考电工证吗 ?”“ 怎么报名…

📰

大专考电工证要考几门怎么报名?3门就能上岗找工作

大专考电工证要考几门怎么报名?3门就能上岗找工作 大专生考电工证想快速上岗, 怎么报名 是头等大事,但你真的知道要考几门吗?别急,先搞清楚这些,才能避免浪费时间又花钱。 大专考电工证要考几门?3门考试就能拿证 大专生考电工证要考几门…

📰

住建厅电工证能用么网上查询怎么操作

住建厅电工证能用么网上查询怎么操作 怕考不过白交培训费?住建厅电工证能用么?网上查询是不是特别麻烦?我来给你说清楚,别再被培训机构忽悠了。…

📰

电工证复审要体检吗 电工资质如何办理怎么报名

电工证复审要体检吗 电工资质如何办理怎么报名 工地太忙根本没时间复习考试,电工证复审又到了,真有点发愁。今天咱们就来聊聊 电工证复审要体检吗 ,以及 怎么报名 、考试内容、流程注意事项,让你少走弯路,轻松搞定复审。…

📰

高压作业的电工证官方回应:到期换证流程全解析,找工作必备!

高压作业的电工证官方回应:到期换证流程全解析,找工作必备! 你是不是也遇到过这种情况:手头的高压作业电工证快到期了,但又找不到靠谱的换证渠道,生怕耽误了上岗时间?别急,官方回应来了!今天咱们就从焦作某项目现场管理员老李的真实案例出发,带你了…

TODAY

今日更新

THIS WEEK

本周精选

THIS MONTH

本月热门

读完文章,想聊聊您的网站?

告诉我们您的行业与需求,资深顾问一对一梳理方案与报价,全程免费。

📞 💬