小旭讲解 LeetCode. 207 课程表
文章目录

  • 原题
  • 思路一 – 拓扑排序
  • 参考

原题

你这个学期必须选修 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

思路一 – 拓扑排序

这是一道图的问题,题目给定了若干条有向边,我们可以使用这些有向边构建出一个图。构建的方法有两种:邻接表,邻接矩阵。

这里面我们使用比较简单的方式 —— 邻接矩阵 表示一个有向图。形如下面:

   0列 1列 0行 1  1 1行 0  1

上面 (0, 1) 的值为 1,代表存在一个从 0 出发,指向 1 的一条边。

上面 (1, 0) 的值为0,代表不存在一个从 1 出发,指向 0 的一条边。

题目实际上是要求判断这个有向图中是否存在环。如果存在环那么返回 false,否则返回 true。

判断有向图中是否有环可以使用拓扑排序,关于拓扑排序,我曾经录了一个视频来讲解,有兴趣的同学可以看下:拓扑排序 —— 小旭讲解 LeetCode 269. Alien Dictionary – EP14。

代码

class Solution { public:     bool canFinish(int n, vector<vector<int>>& ps) {         vector<vector<int>> m(n + 5, vector<int>(n + 5, 0));         vector<int> id(n + 5, 0);         for (auto &p : ps) {             m[p[1]][p[0]] = 1;             id[p[0]]++;         }         queue<int> q;         for (int i = 0; i < n; ++i) {             if (id[i] == 0) q.push(i);         }         int cnt = 0;         while (!q.empty()) {             auto no = q.front();             q.pop();             ++cnt;             for (int nno = 0;nno < n; ++nno) {                 if (m[no][nno] == 0) continue;                 if (--id[nno] == 0) q.push(nno);             }         }         return cnt == n;     } };

复杂度分析

时间复杂度:O(V + E) V 代表图的节点数,E 代表图的边数
空间复杂度:O(V^2)

思路二 – 深度优先搜索

在 DFS 时,我们将节点进行标记,一共有三种状态:

  • 未访问 0
  • 访问中 1
  • 已访问 2

如果在搜索时,搜到了一个在访问中的节点,那么此时出现了环。即返回 false。

代码

class Solution { public:     vector<vector<int>> ps, m;     // vis 0 未访问 1 访问中 2 已访问     vector<int> vis;     int n;     bool dfs(int no) {         if (vis[no] == 1) return false; // 有环         if (vis[no] == 2) return true; // 曾经搜索过         vis[no] = 1;         for (int nno = 0; nno < n; ++nno) {             if (m[no][nno] == 0) continue;             if (!dfs(nno)) return false;         }         vis[no] = 2;         return true;     }     bool canFinish(int _n, vector<vector<int>>& _ps) {         n = _n, ps = _ps;         m = vector<vector<int>>(n, vector<int>(n, 0));         vis = vector<int>(n, 0);         for (auto &p : ps) {             m[p[1]][p[0]] = 1;         }         for (int no = 0; no < n; ++no) {             if (!dfs(no)) return false;         }         return true;     } };

复杂度分析

时间复杂度:O(V + E)
空间复杂度:O(V^2)

参考

[1]. LeetCode 原题. https://leetcode-cn.com/problems/course-schedule/
[2]. 拓扑排序 —— 小旭讲解 LeetCode 269. Alien Dictionary – EP14. https://www.bilibili.com/video/BV1CJ411S7Wj

小旭讲解 LeetCode. 207 课程表leetcode刷题题解部分资料来自网络,侵权毕设源码联系删除

区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站
部分资料来自网络,侵权联系删除!
资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 小旭讲解 LeetCode. 207 课程表leetcode刷题题解