LeetCode每日一题 207. 课程表

2023-12-21 19:30:18

题目描述

给定一个整数 numCourses 表示一学期必须选修的课程数目,以及一个课程先修关系数组 prerequisites,其中 prerequisites[i] = [ai, bi] 表示如果要学习课程 ai 则必须先学习课程 bi。判断是否可能完成所有课程的学习,如果可以,返回 true;否则,返回 false

算法思路

这个问题可以通过拓扑排序来解决,拓扑排序是一种对有向无环图(DAG)进行排序的方法。如果存在一种合法的学习顺序,那么图中一定不存在环。以下是解决这个问题的步骤:

  1. 创建一个有向图 graph,以及一个入度数组 inDegree

  2. 遍历 prerequisites 数组,将课程之间的先修关系构建成有向边,同时更新每门课程的入度。

  3. 将入度为0的课程入队,这些课程可以作为起始节点进行拓扑排序。

  4. 在循环中,依次将入度为0的课程出队,并更新与它相邻的课程的入度。如果更新后的入度为0,将该课程入队。

  5. 继续循环,直到队列为空。如果拓扑排序过程中没有出现环(即剩余的课程数为0),则可以完成所有课程学习,返回 true;否则返回 false

代码实现

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> graph(numCourses, vector<int>());
        vector<int> inDegree(numCourses, 0);

        // 构建有向图和入度数组
        for (const vector<int>& pre : prerequisites) {
            graph[pre[1]].push_back(pre[0]);
            inDegree[pre[0]]++;
        }

        queue<int> q;

        // 将入度为0的课程入队
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                q.push(i);
            }
        }

        while (!q.empty()) {
            int curr = q.front();
            q.pop();
            numCourses--;

            // 更新与当前课程相邻的课程的入度
            for (int neighbor : graph[curr]) {
                if (--inDegree[neighbor] == 0) {
                    q.push(neighbor);
                }
            }
        }

        return numCourses == 0;
    }
};

文章来源:https://blog.csdn.net/wxhzly__030/article/details/132778974
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。