[Day 27] Leetcode 207. Course Schedule (C++)

前言

今天选择的是TOP 100 LIKED的另外一题~207. Course Schedule，牵涉到一个经典的演算法，一起来看看吧！

想法

这题的题目是给了一堆课的先修要求，然後要检查是否可以在不违反这些先修课要求的条件下完成它。
而这题首要之务就是先转换题目成比较可以使用的格式，因此我想：先把修课要求存成map，如下：

// for every course, record the course that would study after that
unordered_map<int, vector<int>> preCourseRev;
for(int i=0;i<prerequisites.size();++i){
    preCourseRev[prerequisites[i][0]].push_back(prerequisites[i][1]);
}

然後我就卡住了，一开始的判断想说这题应该是要看有没有出现死结，所以就针对每一堂课，去追溯他的先修课，DFS去追每一堂课的前面，直到出现重复的。然後就TLE了XD：

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        // record the prerequisites first
        map<int, vector<int>> preCourse;
        for(int i=0;i<prerequisites.size();++i){
            preCourse[prerequisites[i][0]].push_back(prerequisites[i][1]);
        }
        // keep record to required courses
        vector<int> seen(numCourses, 0);
        //int checked[numCourses]={0};
        
        
        // check for every courses
        for(int i=0;i<numCourses;++i){
            seen={0};

            // if not checked yet
            //if(checked[i]==0){
                // trace to see if prerequisites conflict
                //seen[i] = 1;
                //for(int j : preCourse[i]){
            if(checkForCourse(i, seen, preCourse)==false){
                return false;
            }
       // }
            //}
        }
        return true;
    }
    bool checkForCourse(int i, vector<int> &seen,map<int, vector<int>> &preCourse){
        if(seen[i]==1){
            return false;
        }
                

        else{
            seen[i]=1;
            for(int j: preCourse[i]){
                if(checkForCourse(j, seen, preCourse)==false){
                        return false;
                }
            }
            seen[i]=0;
            //checked[i]==1;
            return true;
        }
    }
};

检讨结果是我这样重复得计算搞得太多，等於每堂课分岔再分岔去它前面修过的课，针对每次修过的课又检查好几次，其实每次应该检查自己就好了。
不过其实这题应用的是这个重点─Topological sort演算法，可以参考这边提供的说明Topological Ordering。
整个演算法的重点就是：

• 前置作业─课堂计算

1. 同前面所说，先转换成每一堂课的map
2. 计算每堂课有几门先修课
3. 计算有几堂课没有先修课，那就是接下来可以作为第一堂课的课，我们把它存在一个queue里

• 遍历每一堂课
  现在我们要来排序了，我们总共要修n堂课，所以会遍历n堂，而起点就应该是没有先修课的一堂课

4. 如果还没遍历完n堂课，但却每堂课都有先修课，代表其中有cycle，找不到一个起点，所以可以直接return false
5. 如果有没有先修课的课，我们就把其中一堂课从QUEUE里取出来修完它
6. 修完它我们就不管它了，直接把它需要的课设为-1个
7. 针对其他堂课，我们检查如果先修课包含刚刚那门修掉的课，那它们的先修课数目就-1，如果变成0了，就可以加到前面那个queue里
8. 持续4~7的步骤，直到违反4而回传false或顺利遍历完回传true
   写出来的解法如下，可以accepted：

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        // topological sort, to find the starting point
        // compute the number of course that have to study before that course
        vector<int> degrees(numCourses,0);
        for(int i=0;i<prerequisites.size();++i){
            ++degrees[prerequisites[i][1]];
        }
        
        // for every course, record the course that would study after that
        map<int, vector<int>> preCourseRev;
        for(int i=0;i<prerequisites.size();++i){
            preCourseRev[prerequisites[i][0]].push_back(prerequisites[i][1]);
        }
        
        
        // a queue to record 0 degress point
         queue<int> q;
        for (int i=0; i<numCourses; ++i){
            if (degrees[i] == 0)
                q.push(i);
        }
        int cur=0;
        // detect if cycle
        for (int i=0; i<numCourses; ++i)
        {
            // from 0 degree point
            if (q.empty()){
                // no starting point. There are cycles.
                return false;
            }
            // starting from the first 0 degree point(class without prerequisities)
            cur = q.front();
            q.pop();
            // set to -1 indicates the point has been checked
            degrees[cur] = -1;
 
            // update the course requires cur
            for (int j: preCourseRev[cur])
            {
                --degrees[j];
                if (degrees[j]==0){
                    q.push(j);
                } 
            }
        }
        return true;
    }      
};

这是按照我对此演算法理解写出来的版本，後来优化前面两件事可以一起做+可以提早结束如下：
优化的是把前面1.2的计算写在同一个for里完成，并在最後加一个判断如果queue的数量=剩下课程的数量，代表大家都没先修课了，可以随便按照顺序也没关系，因此可以直接回传true。

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        // topological sort, to find the starting point
        // compute the number of course that have to study before that course
        vector<int> degrees(numCourses,0);
        
        // for every course, record the course that would study after that
        map<int, vector<int>> preCourseRev;
        for(int i=0;i<prerequisites.size();++i){
            preCourseRev[prerequisites[i][0]].push_back(prerequisites[i][1]);
            ++degrees[prerequisites[i][1]];
        }
        
        
        // a queue to record 0 degress point
         queue<int> q;
        for (int i=0; i<numCourses; ++i){
            if (degrees[i] == 0)
                q.push(i);
        }
        int cur=0;
        // detect if cycle
        for (int i=0; i<numCourses; ++i)
        {
            // from 0 degree point
            if (q.empty()){
                // no starting point. There are cycles.
                return false;
            }
            // starting from the first 0 degree point(class without prerequisities)
            cur = q.front();
            q.pop();
            // set to -1 indicates the point has been checked
            degrees[cur] = -1;
 
            // update the course requires cur
            for (int j: preCourseRev[cur])
            {
                --degrees[j];
                if (degrees[j]==0){
                    q.push(j);
                } 
            }
            // if there are no links now could be stop early
            if(q.size()==numCourses-i){
                return true;
            }
        }
        return true;
    }      
};

结语

说好的sum系列一直没有继续XD
倒数第4天了，继续来完成它们吧！