建设网站的分析,wordpress获取浏览人信息,软件开发后端,那些网站是静态本专栏内容为#xff1a;算法学习专栏#xff0c;分为优选算法专栏#xff0c;贪心算法专栏#xff0c;动态规划专栏以及递归#xff0c;搜索与回溯算法专栏四部分。 通过本专栏的深入学习#xff0c;你可以了解并掌握算法。 #x1f493;博主csdn个人主页#xff1a;小… 本专栏内容为算法学习专栏分为优选算法专栏贪心算法专栏动态规划专栏以及递归搜索与回溯算法专栏四部分。 通过本专栏的深入学习你可以了解并掌握算法。 博主csdn个人主页小小unicorn ⏩专栏分类算法从入门到精通 代码仓库小小unicorn的代码仓库 关注我带你学习编程知识 专题十八 课程表算法原理 课程表 II算法原理 总结 课程表
你这个学期必须选修 numCourses 门课程记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出其中 prerequisites[i] [ai, bi] 表示如果要学习课程 ai 则 必须 先学习课程 bi 。
例如先修课程对 [0, 1] 表示想要学习课程 0 你需要先完成课程 1 。 请你判断是否可能完成所有课程的学习如果可以返回 true 否则返回 false 。 算法原理
本题题意要先搞懂举个例子 假设传入的这个数组以[1,0]来说它的意思就是要想先修1就必须先学习0这门课程依次内推。想这个我们可以画个箭头好理解0-1 意思就是学1要先学0
分析到这我们就可以把这个数组抽象出来 这个图是不是很熟悉这不就是我们的有向图吗
看一下题目问的啥问能否修完那这问题的本质不就是给这个图能否拓扑排序或者问这个图是不是有环.
分析到这其实就可以动手写代码了但是我们前言末尾说到过实现拓扑排序的前提是要建图。我们先打一下理论基础看如何建图
首先如何灵活建图的前提我们要合理用我们的容器。 其次要看数据的稠密也就是数据量我们通常有两种办法
邻接矩阵邻接表 邻接矩阵市面上书籍讲的很多这里我们采用邻接表的形式。 什么是邻接表呢 以刚才例子为例我们把每个位置相连的点都放在一排所形成的这个表就是邻接表。
可能有人好奇那我们岂不是要实现一个链表才能形成上面的对应关系其实不然我们用数组就可以模拟代替链表。
接下来我们可以选择合适的容器也就是代码如何实现这里我们给出两种
vector 我们在vector里嵌套一个vector
vectorvectorint edge;//edge边的意思为什么二维数组就可以呢 我们让其下标具有对应关系咱们得邻接表不就出来了。
哈希表
用哈希表来实现邻接表
unordered_mapint,vectorint edge;
unordered_mapstring,vectorstring edge;用哈希来反映映射也是可以的。
代码实现
class Solution
{
public:bool canFinish(int n, vectorvectorint prerequisites) {//1.准备工作unordered_mapint,vectorint edge;//邻接表存图//vectorvectorint edge(n);vectorint in(n);//用来标记入度//2.建图for(auto e:prerequisites){int ae[0],be[1]; //b-a的一条边//拿到b的这条边//把a插入到b的后面edge[b].push_back(a);//有一条边指向a了a入度in[a];}//3.拓扑排序queueint q;//(1)把所有入度为0的点加入到队列中for(int i0;in;i){//入度为0if(in[i]0)//加入队列q.push(i);}//2bfswhile(q.size()){int tq.front();q.pop();//拿出点后要把这个点相连的边删掉for(int a:edge[t]){//入度--in[a]--;//如果入度为0进入队列if(in[a]0)q.push(a);}}//4.判断是否有环for(int i0;in;i){if(in[i])return false;} return true;}
};课程表 II
现在你总共有 numCourses 门课需要选记为 0 到 numCourses - 1。给你一个数组 prerequisites 其中 prerequisites[i] [ai, bi] 表示在选修课程 ai 前 必须 先选修 bi 。
例如想要学习课程 0 你需要先完成课程 1 我们用一个匹配来表示[0,1] 。 返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序你只要返回 任意一种 就可以了。如果不可能完成所有课程返回 一个空数组 。
算法原理
本题跟课程表一模一样只是返回的结果不一样本题要返回一个序列所以我们用一个数组统计一下信息即可。
代码实现
class Solution
{
public:vectorint findOrder(int n, vectorvectorint prerequisites) {//1.准备工作vectorvectorint edge(n);//用来储存图//unordered_mapint,vectorint edge;vectorint in(n);//用来标记入度//2.建图for(auto e:prerequisites){int ae[0],be[1]; //b-a的一条边//把a插入到b的后面edge[b].push_back(a);//in[a];}//3.拓扑排序queueint q;vectorint ret;//(1)把所有入度为0的点加入到队列中for(int i0;in;i){//入度为0if(in[i]0)//加入队列q.push(i);}//2bfswhile(q.size()){int tq.front();q.pop();ret.push_back(t);for(int a:edge[t]){//入度--in[a]--;//如果入度为0进入队列if(in[a]0)q.push(a);}}//4.判断是否有环if(ret.size()n)return ret;else return {};}
};总结
其实用代码建图很简单对于代码其实也就两三行的事情
准备工作
//数组模拟
vectorvectorint edge(n)//n是大小
//哈希表模拟
unordered_mapint,vectorint edge;
//入度
vectorint in(n);建图
for(auto e:prerequisites)
{int e[0]a,e[1]b; b-a;//找到b这条边e[b].push_back(a);//有一条边指向了a//a入度in[a];
}拓扑排序
排序就根据前言分析的步骤实现。
