LeetCode207 课程表

问题：课程表

现在你总共有 n 门课需要选，记为 0 到 n-1。

在选修某些课程之前需要一些先修课程。例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]

给定课程总量以及它们的先决条件，判断是否可能完成所有课程的学习？

示例 1:

输入: 2, [[1,0]]

输出: true

解释: 总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。所以这是可能的。

示例 2:

输入: 2, [[1,0],[0,1]]

输出: false

解释: 总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0；并且学习课程 0 之前，你还应先完成课程 1。这是不可能的。

说明:

输入的先决条件是由边缘列表表示的图形，而不是邻接矩阵。详情请参见图的表示法。
你可以假定输入的先决条件中没有重复的边。

提示:

这个问题相当于查找一个循环是否存在于有向图中。如果存在循环，则不存在拓扑排序，因此不可能选取所有课程进行学习。
通过 DFS 进行拓扑排序 - 一个关于Coursera的精彩视频教程（21分钟），介绍拓扑排序的基本概念。
拓扑排序也可以通过 BFS 完成。

链接：https://leetcode-cn.com/problems/course-schedule/description/

分析：

1，一门课的先修课可能有多个，只要有一个没学就没法学

2，如果进行一轮后，没有新增学到的课，那么后续也不会再增加了

3，如果学到的课就是课程数量，则学了所有的，否则学不完。

所以可以设定如下数据结构：

class Class

{

public:

    int Num=INT_MAX; //为止

    int Status=; // 未学习

    vector<int> dps;

};

Num是课程编号，Status是课程状态，0表示没学，1表示学了，dps表示以来课程。

可以假设所有的课程都不依赖任何课，初始化完成后，根据依赖关系更新，然后找到不依赖其他课的课程，

以没有先修课的课程为基础，持续更新，直到不再新增学到的课程位置。

更新方式为：如果一个课程的先修课都已经学过了，这门课也可以学习。

AC Code：

class Class

{

public:

    int Num=INT_MAX; //为止

    int Status=; // 未学习

    vector<int> dps;

};

class Solution {

public:

    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {

        bool ret = false;

        //如果能找到一个起始课程，即不依赖任何课程的，从这个开始学习所有

        //如果找不到，则不能进行

        vector<Class> classes;

        for (int i = ; i < numCourses; i++)

        {

            Class tmp;

            tmp.Num = i;

            tmp.Status = ;

            tmp.dps = vector<int>();

            classes.emplace_back(tmp);

        }

        int n = prerequisites.size();

        sort(prerequisites.begin(), prerequisites.end());

        for (int i = ; i <n; i++)

        {

            int tmpnum = prerequisites[i].first;

            int depnum = prerequisites[i].second;

            for (int j = ; j < classes.size(); j++)

            {

                if (classes[j].Num == tmpnum)

                {

                    classes[j].dps.emplace_back(depnum);

                    break;

                }

            }

        }

        //找到所有的不依赖其他的课程，并且从哪些出发得打所有的不依赖的课程

        int learned = ;

        vector<int> learnedclass;

        for (int i = ; i < classes.size(); i++)

        {

            if (classes[i].dps.size() == )

            {

                classes[i].Status = ;

                learned++;

                learnedclass.emplace_back(classes[i].Num);

            }

        }

        while (true)

        {

            int currentlearned = learned;

            for (int i = ; i < classes.size(); i++)

            {

                if (classes[i].Status == )

                {

                    continue;

                }

                else

                {

                    //这门课没学，看先修课有没有学

                    vector<int> tmpre = classes[i].dps;

                    int learnflag = ;

                    for (int j = ; j < tmpre.size(); j++)

                    {

                        if (find(learnedclass.begin(), learnedclass.end(), tmpre[j]) == learnedclass.end())

                        {

                            learnflag = ; //有先修课没学，学不了了

                            break;

                        }

                    }

                    if (learnflag == )

                    {

                        //这门课可以学

                        classes[i].Status = ;

                        learned++;

                        learnedclass.emplace_back(classes[i].Num);

                    }

                }

            }

            if (currentlearned == learned)

            {

                //没有增加学习的课程，可以结束了

                //if(learned == )

                return learned == numCourses;

            }

        }

        return ret;

    }

};

其他：

1.QQ群里有人提到这个题，周赛第四题没搞懂dp状态转移方程，解决这个问题消磨时间吧。

提示中有提到图论等知识，不过也就学数据结构的时候学过这个，平时不怎么用，或者说不知道主动去用，没用图论的知识，虽然过了，效率比较低，以后有机会好好补补相关知识。

2.太冷动手，没太大兴趣看了，不过可以优化的地方有，一门课是否能学，看其先修课是否已经学过了，那么下一次更新的时候，再次查看就浪费时间，可以看缺了哪些课，这样待处理的数据会逐渐减少避免重复运算。

3.用时最短code：

 static const auto _ = []()

 {

     ios::sync_with_stdio(false);

     cin.tie(nullptr);

     return nullptr;

 }();

 class Solution {

     vector<int> *vex;   //vex[a]={b,c}：要学习a，须先学b,c

     char *visit;        //0：从未访问，1：正在访问，2：曾经访问

     //若成环，返回false

     bool DFS(int vID){

         if(visit[vID]==)

             return false;   //成环了

         if(visit[vID]==){  //0：从未访问

             visit[vID]=;   //1：正在访问

             for(int i=;i<vex[vID].size();++i){

                 if(!DFS(vex[vID][i]))return false;  //成环了

             }

             visit[vID]=;   //2：曾经访问

         }

         return true;    //访问过了

     }

 public:

     bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {

         vex= new vector<int>[numCourses];

         visit= new char[numCourses];

         fill(visit,visit+numCourses,);         //0：从未访问

         for(int i=;i<prerequisites.size();++i){

             auto &edge=prerequisites[i];

             vex[edge.first].push_back(edge.second);  //[1,0]，学习课程 1 之前，你需要完成课程 0。

         }

         //逐个访问

         for(int i=;i<numCourses;++i){

             if(!DFS(i))return false;

         }

         return true;   //没有成环即可

     }

 };

巴特西

LeetCode207 课程表

最新文章

热门文章