课程表

难度:

标签:

题目描述

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [a_i, b_i] ，表示如果要学习课程 a_i 则必须先学习课程 b_i。

例如，先修课程对 [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 <= 2000
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
0 <= a_i, b_i < numCourses
prerequisites[i] 中的所有课程对 互不相同

代码结果

运行时间: 23 ms, 内存: 17.1 MB

// 思路：同样使用Kahn's Algorithm，但使用Java Stream来处理集合操作。
import java.util.*;
import java.util.stream.*;
 
public class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] indegree = new int[numCourses];
        Map<Integer, List<Integer>> graph = new HashMap<>();
        for (int i = 0; i < numCourses; i++) {
            graph.put(i, new ArrayList<>());
        }
        for (int[] prereq : prerequisites) {
            graph.get(prereq[1]).add(prereq[0]);
            indegree[prereq[0]]++;
        }
        Queue<Integer> queue = IntStream.range(0, numCourses)
                                        .filter(i -> indegree[i] == 0)
                                        .boxed()
                                        .collect(Collectors.toCollection(LinkedList::new));
        int count = 0;
        while (!queue.isEmpty()) {
            int course = queue.poll();
            count++;
            for (int next : graph.get(course)) {
                if (--indegree[next] == 0) {
                    queue.offer(next);
                }
            }
        }
        return count == numCourses;
    }
}

解释

方法:

这个题解使用了拓扑排序的思想。首先根据题目给定的先修课程关系构建一个有向图，每个课程代表图中的一个节点，如果课程A是课程B的先修课，则在图中添加一条从B指向A的有向边。同时统计每个课程的入度，即每个课程有多少门先修课程。然后将所有入度为0的课程加入队列，代表可以直接修读的课程。接下来进行BFS，每次从队列取出一门课程，将其指向的所有后继课程的入度减1，如果某个后继课程的入度变为0，则将其加入队列。最后判断是否学完了所有的课程，即`numCourses`是否减为0。

时间复杂度:

O(V+E)

空间复杂度:

O(V)

代码细节讲解

🦆

为什么在构建有向图时，选择从课程bi指向课程ai，而不是从ai指向bi？

▷

在构建有向图时，选择从课程bi指向课程ai是为了反映课程ai必须在课程bi之前完成的关系。这样的表示方法使得入度（每个节点的入边数）直接对应于每个课程的先修课数量，方便在拓扑排序中直接使用入度为0的课程作为起始点。如果从ai指向bi，则需要额外的步骤或转换来识别哪些课程可以最先开始学习，增加了算法的复杂性。

🦆

在算法中，如何处理存在循环依赖的课程结构，例如示例中的[[1,0],[0,1]]？

▷

在存在循环依赖的课程结构中，如[[1,0],[0,1]]，表示课程1依赖课程0，同时课程0又依赖课程1，形成了一个循环。在这种情况下，拓扑排序会发现没有任何课程的入度为0，因此初始队列为空。在BFS执行过程中，队列始终为空，没有课程的入度会被减至0。算法最终会返回false，表示无法完成所有课程的学习。这正是拓扑排序处理循环依赖的方式，即通过检测是否能遍历所有节点来判断是否存在循环依赖。

🦆

算法中提到使用BFS进行拓扑排序，为何不使用DFS，两者在这种场景下有什么优劣势？

▷

在这种场景下，使用BFS进行拓扑排序的优势在于其直观性和易于实现，特别是处理入度和队列的操作直接映射到课程的解锁过程。BFS能够逐层处理，每次都处理当前无依赖（或已解决依赖的）课程，这使得算法的执行逻辑清晰。而DFS虽然也可以用来进行拓扑排序，但其递归性质和后序遍历的特点使得实现相对复杂，尤其是在处理大规模数据时更容易遇到栈溢出的问题。此外，DFS在遇到循环依赖时需要额外的机制（如访问标记）来检测并处理循环，而BFS则通过简单的入度计数自然避免了这一问题。

🦆

在拓扑排序的过程中，如果队列为空但还有未处理的课程，这种情况如何处理？

▷

如果在拓扑排序的过程中队列变为空，但仍有未处理的课程（即仍有课程的入度不为0），这通常意味着存在循环依赖，导致某些课程无法被解锁。在这种情况下，算法应该判断为无法完成所有课程的学习，返回false。这种情况下的空队列表明没有更多的课程可以无先修课程的限制下开始学习，进一步揭示了课程间的依赖关系存在闭环，阻止了某些课程的正常学习顺序。

相关问题

课程表 II

现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequisites[i] = [a_i, b_i] ，表示在选修课程 a_i 前必须先选修 b_i 。

例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。

返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 。

示例 1：

输入：numCourses = 2, prerequisites = [[1,0]]
输出：[0,1]
解释：总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。

示例 2：

输入：numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
输出：[0,2,1,3]
解释：总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。

示例 3：

输入：numCourses = 1, prerequisites = []
输出：[0]

提示：

1 <= numCourses <= 2000
0 <= prerequisites.length <= numCourses * (numCourses - 1)
prerequisites[i].length == 2
0 <= a_i, b_i < numCourses
a_i != b_i
所有[a_i, b_i] 互不相同

以图判树

最小高度树

树是一个无向图，其中任何两个顶点只通过一条路径连接。换句话说，任何一个没有简单环路的连通图都是一棵树。

给你一棵包含 n 个节点的树，标记为 0 到 n - 1 。给定数字 n 和一个有 n - 1 条无向边的 edges 列表（每一个边都是一对标签），其中 edges[i] = [a_i, b_i] 表示树中节点 a_i 和 b_i 之间存在一条无向边。

可选择树中任何一个节点作为根。当选择节点 x 作为根节点时，设结果树的高度为 h 。在所有可能的树中，具有最小高度的树（即，min(h)）被称为 最小高度树 。

请你找到所有的 最小高度树 并按 任意顺序 返回它们的根节点标签列表。

树的高度是指根节点和叶子节点之间最长向下路径上边的数量。

示例 1：

输入：n = 4, edges = [[1,0],[1,2],[1,3]]
输出：[1]
解释：如图所示，当根是标签为 1 的节点时，树的高度是 1 ，这是唯一的最小高度树。

示例 2：

输入：n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]
输出：[3,4]

提示：

1 <= n <= 2 * 10⁴
edges.length == n - 1
0 <= a_i, b_i < n
a_i != b_i
所有 (a_i, b_i) 互不相同
给定的输入保证是一棵树，并且 不会有重复的边

课程表 III

这里有 n 门不同的在线课程，按从 1 到 n 编号。给你一个数组 courses ，其中 courses[i] = [duration_i, lastDay_i] 表示第 i 门课将会持续上 duration_i 天课，并且必须在不晚于 lastDay_i 的时候完成。

你的学期从第 1 天开始。且不能同时修读两门及两门以上的课程。

返回你最多可以修读的课程数目。

示例 1：

输入：courses = [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]
输出：3
解释：
这里一共有 4 门课程，但是你最多可以修 3 门：
首先，修第 1 门课，耗费 100 天，在第 100 天完成，在第 101 天开始下门课。
第二，修第 3 门课，耗费 1000 天，在第 1100 天完成，在第 1101 天开始下门课程。
第三，修第 2 门课，耗时 200 天，在第 1300 天完成。
第 4 门课现在不能修，因为将会在第 3300 天完成它，这已经超出了关闭日期。

示例 2：

输入：courses = [[1,2]]
输出：1

示例 3：

输入：courses = [[3,2],[4,3]]
输出：0

提示:

1 <= courses.length <= 10⁴
1 <= duration_i, lastDay_i <= 10⁴

反转链表实现 Trie (前缀树)