当前位置：首页 > article >正文

leetcode207：课程表

article 2025/1/16 19:03:09

你这个学期必须选修 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] 中的所有课程对 互不相同

步骤1：定义问题性质

问题描述：给定一个课程安排问题，其中有 numCourses 门课程，每门课程都有可能有前置课程要求，即必须先学习某些课程才能学习当前课程。你需要判断是否可以完成所有课程的学习，即是否存在一个有效的学习顺序。

输入：

numCourses: 一个整数，表示课程的总数，范围是 [1, 2000]。
prerequisites: 一个二维数组，其中每个元素是一个长度为2的数组 [ai, bi]，表示要学习课程 ai 必须先学习课程 bi。

输出：

如果可以完成所有课程的学习，返回 true；否则返回 false。

边界条件：

如果没有先修课程 (prerequisites.length == 0)，直接返回 true。
如果课程图中存在环，即存在相互依赖的课程，无法完成所有课程的学习，返回 false。
numCourses 为 1 时，直接返回 true，因为没有前置课程。

步骤2：问题分解与解决方案

构建课程依赖图：
- 将课程与其前置课程建立图结构，这个图应该是有向图，节点是课程，边表示前置依赖关系。
- 如果 prerequisites[i] = [ai, bi]，则在图中有一条从 bi 到 ai 的有向边。
检测有向图是否有环：
- 如果图中存在环，则无法完成所有课程的学习。检测环可以通过深度优先搜索（DFS）来完成。
- 使用一个额外的状态数组来标记每个课程的状态：未访问（0）、正在访问（1）、已访问（2）。如果在 DFS 遍历过程中再次遇到状态为“正在访问”的节点，则表示存在环。
算法设计：
- DFS + 拓扑排序：通过 DFS 遍历图，并在遍历过程中检查是否有环。如果没有环，说明可以完成所有课程。
- 时间复杂度：O(V + E)，其中 V 是课程数，E 是先修课程的数目（即图中的边数）。
- 空间复杂度：O(V + E)，需要存储图和状态信息。
具体实现：
- 使用邻接表表示图。
- 使用 DFS 来检测环，并通过状态数组来避免重复计算。

步骤3：C++代码实现

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        // 创建邻接表
        vector<vector<int>> graph(numCourses);
        // 创建状态数组：0 - 未访问，1 - 正在访问，2 - 已访问
        vector<int> visited(numCourses, 0);
        
        // 构建图
        for (const auto& prereq : prerequisites) {
            graph[prereq[1]].push_back(prereq[0]);
        }

        // 深度优先搜索（DFS）判断是否有环
        for (int i = 0; i < numCourses; ++i) {
            if (visited[i] == 0 && !dfs(graph, visited, i)) {
                return false; // 如果找到环，则返回 false
            }
        }

        return true; // 如果没有环，则返回 true
    }

private:
    // DFS递归函数
    bool dfs(const vector<vector<int>>& graph, vector<int>& visited, int node) {
        // 如果当前节点正在访问中，说明有环
        if (visited[node] == 1) {
            return false;
        }
        
        // 如果当前节点已经访问过，直接返回
        if (visited[node] == 2) {
            return true;
        }
        
        // 标记为正在访问
        visited[node] = 1;
        
        // 递归访问所有相邻的节点
        for (int neighbor : graph[node]) {
            if (!dfs(graph, visited, neighbor)) {
                return false;
            }
        }
        
        // 标记为已访问
        visited[node] = 2;
        
        return true;
    }
};

步骤4：解决问题的启发

图的遍历和环检测：本题启发我们在面对依赖关系问题时，可以将其抽象为一个有向图问题。图的遍历是解决依赖问题的常见方法，尤其是利用 DFS 来检测是否有环，避免死循环。
拓扑排序与排序问题的结合：拓扑排序不仅可以用来解决课程安排问题，还广泛应用于任务调度、项目管理等领域。通过判断是否可以找到一个拓扑排序，我们可以决定是否能够按顺序完成任务。