LeetCode 207. 课程表Course ScheduleJava 实现题目简述一共有“numCourses” 门课程编号“0 ~ numCourses-1”。给定“prerequisites” 数组其中“prerequisites[i] [a, b]” 表示 想学课程 a 必须先学课程 b。判断是否能完成所有课程。本质判断有向图中是否存在环有环则无法完成。思路拓扑排序BFS / Kahn 算法核心思想统计每门课的入度有多少先修依赖把所有入度为 0 的课入队不依赖任何课的课逐个出队学完该课后把它指向的课的入度减 1如果某门课入度变为 0加入队列最终学完的课数 总课数则无环可以学完Java 实现class Solution {public boolean canFinish(int numCourses, int[][] prerequisites) {// 入度数组indegree[i] 表示学课程 i 前需要先学的课程数int[] indegree new int[numCourses];// 邻接表graph[i] 存的是学了课程 i 之后可以学的课程列表ListList graph new ArrayList();for (int i 0; i numCourses; i) {graph.add(new ArrayList());}// 构建图和入度 for (int[] pre : prerequisites) { int course pre[0]; // 想学的课 int need pre[1]; // 先修的课 graph.get(need).add(course); indegree[course]; } // 把所有入度为 0 的课加入队列 QueueInteger queue new LinkedList(); for (int i 0; i numCourses; i) { if (indegree[i] 0) { queue.offer(i); } } int finished 0; // 已学完的课数 while (!queue.isEmpty()) { int curr queue.poll(); finished; // 学完 curr它指向的所有课的入度减 1 for (int next : graph.get(curr)) { indegree[next]--; if (indegree[next] 0) { queue.offer(next); } } } // 全部学完说明无环 return finished numCourses; }}复杂度分析维度 复杂度时间 O(V E)V 为课程数E 为先修关系数空间 O(V E)邻接表 入度数组示例说明输入: numCourses 4, prerequisites [[1,0],[2,0],[3,1],[3,2]]输出: true解释: 合理顺序如 0 → 1 → 2 → 3或 0 → 2 → 1 → 3输入: numCourses 2, prerequisites [[1,0],[0,1]]输出: false解释: 0 依赖 11 依赖 0形成环无法完成常见坑点入度含义别搞反“[a, b]” 是 a 依赖 b所以 b 指向 aa 的入度 1邻接表存的是学完某课后能学的课方向别存反“finished numCourses” 是判断无环的关键不用人为计数边数延伸DFS 三色标记法 也能判环白/灰/黑思路和 BFS 等价如果题目问 输出一个合法的修课顺序那就是 LeetCode 210. 课程表 II只需把“finished” 换成记录顺序的数组即可需要我补充 DFS 判环版 或 LeetCode 210 输出拓扑排序 的 Java 实现吗