东莞政务网站建设方案,wordpress 适合程序员主题,网页设计公司背景,佛山销售型网站建设目录
207. 课程表
题目描述#xff1a;
实现代码与解析#xff1a;
拓扑排序
210. 课程表 II
题目描述#xff1a;
实现代码与解析#xff1a;
拓扑排序
原理思路#xff1a; 207. 课程表
题目描述#xff1a; 你这个学期必须选修 numCourses 门课程#xff0…目录
207. 课程表
题目描述
实现代码与解析
拓扑排序
210. 课程表 II
题目描述
实现代码与解析
拓扑排序
原理思路 207. 课程表
题目描述 你这个学期必须选修 numCourses 门课程记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出其中 prerequisites[i] [ai, bi] 表示如果要学习课程 ai 则 必须 先学习课程 bi 。
例如先修课程对 [0, 1] 表示想要学习课程 0 你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习如果可以返回 true 否则返回 false 。
示例 1
输入numCourses 2, prerequisites [[1,0]]
输出true
解释总共有 2 门课程。学习课程 1 之前你需要完成课程 0 。这是可能的。
示例 2
输入numCourses 2, prerequisites [[1,0],[0,1]]
输出false
解释总共有 2 门课程。学习课程 1 之前你需要先完成课程 0 并且学习课程 0 之前你还应先完成课程 1 。这是不可能的。提示
1 numCourses 20000 prerequisites.length 5000prerequisites[i].length 20 ai, bi numCoursesprerequisites[i] 中的所有课程对 互不相同
实现代码与解析
拓扑排序
class Solution {
public:vectorint h vectorint(2010, -1), e vectorint(20010, 0), ne vectorint(20010, 0), d vectorint(2010, 0);int idx 0, cnt 0;void add(int a, int b){e[idx] b; ne[idx] h[a]; h[a] idx;}// 拓扑排序bool topsort(int n){queueint q; // 队列for (int i 0; i n; i)if (d[i] 0) q.push(i); // 入度为 0的入队while(q.size()){int t q.front();cnt;q.pop(); // bfsfor (int i h[t]; ~i; i ne[i]){int j e[i];d[j]--; // 此节点入度减一if(d[j] 0) q.push(j); // 若入度减为0入队}}if (cnt n) return 0; // 入队的结点小于总结点数else return 1;}bool canFinish(int numCourses, vectorvectorint prerequisites) {for (int i 0; i prerequisites.size(); i){add(prerequisites[i][0], prerequisites[i][1]);d[prerequisites[i][1]]; // 入度}if (topsort(numCourses) 0) return false;else return true;}
};
210. 课程表 II
题目描述 现在你总共有 numCourses 门课需要选记为 0 到 numCourses - 1。给你一个数组 prerequisites 其中 prerequisites[i] [ai, bi] 表示在选修课程 ai 前 必须 先选修 bi 。
例如想要学习课程 0 你需要先完成课程 1 我们用一个匹配来表示[0,1] 。
返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序你只要返回 任意一种 就可以了。如果不可能完成所有课程返回 一个空数组 。
示例 1
输入numCourses 2, prerequisites [[1,0]]
输出[0,1]
解释总共有 2 门课程。要学习课程 1你需要先完成课程 0。因此正确的课程顺序为 [0,1] 。示例 2
输入numCourses 4, prerequisites [[1,0],[2,0],[3,1],[3,2]]
输出[0,2,1,3]
解释总共有 4 门课程。要学习课程 3你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
因此一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3]。
示例 3
输入numCourses 1, prerequisites []
输出[0]提示
1 numCourses 20000 prerequisites.length numCourses * (numCourses - 1)prerequisites[i].length 20 ai, bi numCoursesai ! bi所有[ai, bi] 互不相同
实现代码与解析
拓扑排序
class Solution {
public:vectorint h vectorint(2010, -1), e vectorint(20010, 0), ne vectorint(20010, 0), d vectorint(2010, 0), top vectorint(2010, 0);int idx 0, cnt 0;void add(int a, int b){e[idx] b; ne[idx] h[a]; h[a] idx;}// 拓扑排序bool topsort(int n){queueint q; // 队列for (int i 0; i n; i)if (d[i] 0) q.push(i); // 入度为 0的入队while(q.size()){int t q.front();top[cnt] t;q.pop(); // bfsfor (int i h[t]; ~i; i ne[i]){int j e[i];d[j]--; // 此节点入度减一if(d[j] 0) q.push(j); // 若入度减为0入队}}if (cnt n) return 0; // 入队的结点小于总结点数else return 1;}vectorint findOrder(int numCourses, vectorvectorint prerequisites) {for (int i 0; i prerequisites.size(); i){add(prerequisites[i][1], prerequisites[i][0]);d[prerequisites[i][0]]; // 入度}if (topsort(numCourses) 0) return {};else return vectorint(top.begin(), top.begin() numCourses);}
};
原理思路 其实两道题基本上差不多就是一个需要返回顺序一个不用返回。 本质上都是拓扑排序的基本运用一点都不用改的。
拓扑排序详解带有C模板_Cosmoshhhyyy的博客-CSDN博客 不懂的可以看我之前写的拓扑排序解析。
