LeetCode题练习与总结：课程表--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 <= 2000
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
0 <= ai, bi < numCourses
prerequisites[i] 中的所有课程对 互不相同

二、解题思路

这个问题可以通过检测课程安排图中是否存在环来解决。如果存在环，则不可能完成所有课程，因为环意味着至少有一门课程在开始之前需要自己作为先修课程。

可以使用深度优先搜索（DFS）来检测图中的环。以下是解题步骤：

建立课程之间的邻接表表示图结构。
使用一个数组来记录访问状态，可能的值有三种：未访问（0）、正在访问（1）和已访问（2）。
对于图中的每个节点，使用DFS遍历其所有邻接节点。
在DFS过程中，如果遇到正在访问的节点，则表示存在环，返回false。
如果节点未访问，则标记为正在访问，并继续DFS。
完成DFS后，标记节点为已访问。
如果所有节点都可以完成DFS且没有发现环，则返回true。

三、具体代码

class Solution {public boolean canFinish(int numCourses, int[][] prerequisites) {// 建立邻接表List<List<Integer>> adjList = new ArrayList<>(numCourses);for (int i = 0; i < numCourses; i++) {adjList.add(new ArrayList<>());}for (int[] prerequisite : prerequisites) {adjList.get(prerequisite[1]).add(prerequisite[0]);}// 访问状态数组，0未访问，1正在访问，2已访问int[] visited = new int[numCourses];// 对每个节点进行DFSfor (int i = 0; i < numCourses; i++) {if (!dfs(i, adjList, visited)) {return false;}}return true;}private boolean dfs(int node, List<List<Integer>> adjList, int[] visited) {// 如果节点正在访问，说明存在环if (visited[node] == 1) {return false;}// 如果节点已访问，无需再次访问if (visited[node] == 2) {return true;}// 标记节点为正在访问visited[node] = 1;// 遍历所有邻接节点for (int neighbor : adjList.get(node)) {if (!dfs(neighbor, adjList, visited)) {return false;}}// 标记节点为已访问visited[node] = 2;return true;}
}

四、时间复杂度和空间复杂度

1. 时间复杂度

建立邻接表：
- 遍历所有课程来初始化邻接表的时间复杂度是 O(numCourses)。
- 遍历所有先修课程关系来填充邻接表的时间复杂度是 O(prerequisites.length)。
- 因此，建立邻接表的总时间复杂度是 O(numCourses + prerequisites.length)。
深度优先搜索 (DFS)：
- 对于每个课程，我们可能需要遍历其所有邻接节点。在最坏的情况下，这可能导致对图中的每个节点和边都进行一次访问。
- 假设图中有 E 条边，那么 DFS 的总时间复杂度是 O(V + E)，其中 V 是顶点数（在这里是课程数 numCourses），E 是边数（在这里是 prerequisites.length）。
- 因此，DFS 的总时间复杂度是 O(numCourses + prerequisites.length)。

综上所述，总的时间复杂度是 O(numCourses + prerequisites.length)。

2. 空间复杂度

邻接表：
- 邻接表存储了所有课程和它们对应的邻接节点，每个课程对应一个列表，列表的大小取决于先修课程的数量。
- 因此，邻接表的空间复杂度是 O(numCourses + prerequisites.length)。
访问状态数组：
- 这个数组存储了每个节点的访问状态，大小是 numCourses。
- 因此，访问状态数组的空间复杂度是 O(numCourses)。
递归栈：
- DFS 的递归调用会使用系统栈，在最坏情况下，如果图是一个完全连通的图，那么递归栈的深度可能是 O(numCourses)。
- 因此，递归栈的空间复杂度是 O(numCourses)。

综上所述，总的空间复杂度是 O(numCourses + prerequisites.length)，因为邻接表和访问状态数组是主要的存储结构，而递归栈的空间复杂度通常包含在 DFS 的最坏情况空间复杂度中。

五、总结知识点

数据结构：
- 数组（Array）：用于存储访问状态。
- 列表（List）：用于构建邻接表，存储每个节点的邻接节点。
- 集合（ArrayList）：是 List 接口的一个实现，提供了动态数组的操作。
图论：
- 邻接表（Adjacency List）：用于表示图的一种数据结构，适用于稀疏图。
- 深度优先搜索（DFS）：是一种用于遍历或搜索树或图的算法。
递归：
- 递归是 DFS 实现的核心，用于遍历节点的邻接节点。
算法概念：
- 拓扑排序（Topological Sorting）：虽然代码中没有直接实现拓扑排序，但 DFS 的这种使用方式是拓扑排序判断图是否有环的一部分。
- 环检测（Cycle Detection）：通过 DFS 检测图中是否存在环。
基本编程概念：
- 循环（Loop）：用于初始化邻接表和遍历所有课程。
- 条件语句（Conditional Statements）：用于检查节点的访问状态，决定递归的返回值。
- 状态标记：使用不同的整数值来标记节点的访问状态。

以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。