首页 > 代码库 > [LeetCode]Course Schedule

[LeetCode]Course Schedule

2024-09-18 18:29:26   219人阅读

题目：Course Schedule

给定了n各课程[0,n-1]和课程之间的依赖关系，课程i必须先完成课程j，即：课程i依赖于课程j。判断这些课程能否修完。

思路：

这些课程学习过程类似于拓扑排序，终点是要判断课程学习顺序(依赖关系)中是否有环，如果有环，则不能修完全部课程。

课程可以看成点，课程之间的依赖关系可以看成有向边，所以可通过广度优先搜索和深度优先搜索来判断是否有环。

下面我是通过深度优先搜索来实现的。

注意：

courses.at(p.first).clear();//课程p.first必定无环，所以后面都不用检测它，将其删除

这句话能够大幅度简化循环的次数，提高效率。因为前面检测一边没有环，则后面检测到该位置的课程时，就可以得出无环的结论。

bool LeetCode::canFinish(int numCourses, vector<pair<int, int>>& prerequisites){
    if (numCourses < 1)return true;//没有课程
    if (!prerequisites.size())return true;//没有依赖关系
    vector<vector<int>>courses(numCourses);//第i个课程依赖于courses[i]里的课程
    for (size_t i = 0; i < prerequisites.size(); i++){
        courses.at(prerequisites.at(i).first).push_back(prerequisites.at(i).second);
    }
    vector<bool>visited(numCourses,false);//标记栈中存在的课程
    for (size_t i = 0; i < numCourses; i++){
        for (size_t j = 0; j < courses.at(i).size(); j++){
            stack<pair<int, int>>s;
            s.push(make_pair(i,j));//课程i的依赖数组的第j个位置
            visited.at(i) = true;
            while (!s.empty()){
                auto p = s.top();
                int next = courses.at(p.first).at(p.second);//下一个课程的下标
                if (courses.at(next).size()){//下一个课程是否依赖其他课程
                    if (visited.at(next))return false;//依赖的课程是否已经在栈中，则存在环
                    s.push(make_pair(next, 0));//入栈
                    visited.at(next) = true;//标记
                }
                else{
                    while (p.second + 1 >= courses.at(p.first).size()){//课程p.first全部遍历完，无环
                        visited.at(p.first) = false;//不标记
                        s.pop();
                        if (s.empty())break;
                        courses.at(p.first).clear();//课程p.first必定无环，所以后面都不用检测它，将其删除
                        p = s.top();
                    }
                    if (s.empty())break;//栈空
                    s.pop();
                    s.push(make_pair(p.first, p.second + 1));//课程p.first的下一个依赖课程
                }
            }
        }
        //课程i的所有依赖都不构成环。
        if (courses.at(i).size()) courses.at(i).clear();
    }
    return true;
}

题目：Course ScheduleII

题目的意思和上面的类似，但是下面的需要返回学习的顺序。

思路：

同样按照上面的分析，只需要判断是否有环。同样可以使用广度优先搜索或深度优先搜索。

这里通过求出每个点的入度判断每个课程的顺序。

vector<int> LeetCode::findOrder(int numCourses, vector<pair<int, int>>& prerequisites){
    vector<int>path;//记录合法的路径
    if (numCourses < 1)return path;//没有课程
    vector<vector<int>>courses(numCourses);//第i个课程被courses[i]里的课程依赖
    vector<int>indegrees(numCourses,0);//记录每个点的入度
    for each (auto p in prerequisites){
        courses.at(p.second).push_back(p.first);
        ++indegrees.at(p.first);//计算依赖关系的入度
    }
    queue<int>Q;//先统计入度为0的点
    for (size_t i = 0; i < numCourses; i++){
        if (!indegrees.at(i))Q.push(i);
    }
    for (size_t i = 0; i < numCourses; i++){
        if (!Q.size()){
            if (path.size() < numCourses)path.clear();//有环
            return path;
        }
        int z = Q.front();
        Q.pop();
        path.push_back(z);//记录拓扑排序的路径
        for each (auto p in courses.at(z)){
            --indegrees.at(p);//入度减一
            if (!indegrees.at(p))Q.push(p);//入度减为零时，表示会有其他依赖关系，则可以添加进队列中
        }
    }
    return path;
}

 

[LeetCode]Course Schedule


联系
我们