C语言重构【207】课程表

￡神魔★判官ぃ 2023-01-04 14:56 264阅读 0赞

### 文章目录 ###

*   *   *   *  所有题目源代码：
             *  题目
             *  方案：
             *   *  复杂度计算
                 *  杂记

#### 所有题目源代码： ####

*  [Git地址][Git]

#### 题目 ####

你这个学期必须选修 numCourse 门课程，记为 0 到 numCourse-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。这是不可能的。
     
    
    提示：
    
    输入的先决条件是由 边缘列表 表示的图形，而不是 邻接矩阵 。详情请参见图的表示法。
    你可以假定输入的先决条件中没有重复的边。
    1 <= numCourses <= 10^5

#### 方案： ####

*  方法1，邻接表遍历的拓扑算法，比较原始

class Solution
    { 
    public:
        bool canFinish(int numCourses, vector<vector<int>> &prerequisites)
        { 
            //拓扑算法
            //构造一个图，用邻接矩阵
            vector<int> tmp(numCourses, 0);
            int len = prerequisites.size();
            if (len == 0)
                return true;
            vector<vector<int>> dp(numCourses, vector<int>(1, -1));
    
            //构造邻接表
            for (int i = 0; i < len; i++)
            { 
                tmp[prerequisites[i][0]]++;
                dp[prerequisites[i][1]].push_back(prerequisites[i][0]);
            }
            //执行拓扑算法
            int count = numCourses;
            int jud = 0;
            while (count > 1)
            { 
                jud = 0;
                for (int i = 0; i < numCourses; i++)
                { 
                    if (tmp[i] == 0)
                    { 
                        //入度位0的点，移除
                        jud = 1;
                        for (int j = 1; j < dp[i].size(); j++)
                        { 
                            tmp[dp[i][j]]--;
                        }
                        tmp[i]--;
                        count--;
                        break;
                    }
                }
                if (jud == 0)
                    return false;
            }
            return true;
        }
    };

*  方法2，广度优先算法的拓扑算法,改方法相对于1的改进是每次找入度为0的边不需要遍历一次，即小了很多遍历开销

class Solution
    { 
    public:
        bool canFinish(int numCourses, vector<vector<int>> &prerequisites)
        { 
            //拓扑算法
            //构造一个图，用邻接矩阵
            vector<int> tmp(numCourses, 0);
            vector<vector<int>> dp(numCourses, vector<int>(1, -1));
            vector<int> que;
            int len = prerequisites.size();
    
            if (len == 0)
                return true;
    
            //构造邻接表
            for (int i = 0; i < len; i++)
            { 
                tmp[prerequisites[i][0]]++;
                dp[prerequisites[i][1]].push_back(prerequisites[i][0]);
            }
            //构造广度优先队列
            for (int i = 0; i < numCourses; i++)
            { 
                if (tmp[i] == 0)
                { 
                    // tmp[i]--;
                    //加入队列
                    que.push_back(i);
                }
            }
            //执行拓扑算法
            int index = 0;
            //广度优先算法
            while (index < que.size())
            { 
                for (int i = 1; i < dp[que[index]].size(); i++)
                { 
                    if (tmp[dp[que[index]][i]]-- == 1)
                    { 
                        que.push_back(dp[que[index]][i]);
                    }
                }
                index++;
            }
            return index == numCourses ? true : false;
        }
    };

##### 复杂度计算 #####

*  时间复杂度：O(n+e)：构造n+e，广度优先n+e
 *  空间复杂度：O(n+e)

##### 杂记 #####

*  `Line 1033: Char 34: runtime error: addition of unsigned offset to 0x602000000070 overflowed to 0x60200000006c (stl_vector.h)`
 *  仔细观察，得知overflowed，下溢，再由unsigned offset可知为数组地址偏移（非负），可推出两串两串为地址，前大后小说明下标为-1了，因此可以按照这个方向去改

[Git]: https://github.com/ch98road/leetcode