建什么网站赚钱,wordpress在线安装地址,网站建设工资 优帮云,网站没有做实名认证目录
题目#xff1a;
示例#xff1a;
分析#xff1a;
代码#xff1a; 题目#xff1a; 示例#xff1a; 分析#xff1a;
今天的题目和昨天类似#xff0c;不过今天要我们求出学习所有课程的先后顺序。
昨天只需要我们求出能否学习完所有课程#xff0c;因此…目录
题目
示例
分析
代码 题目 示例 分析
今天的题目和昨天类似不过今天要我们求出学习所有课程的先后顺序。
昨天只需要我们求出能否学习完所有课程因此我们只需要判断构建出的有向图中是否有环即可而今天的题我们就不能简单判断有没有环了。
要返回学习课程的先后顺序最简单最直接的方法就是模拟。
我们跟昨天一样首先先把有向图构建出接着我们再模拟学习模拟之前我们还需要拿一个数组来存放学习课程的顺序以及一个set来记录学过的课程其实数组和set里的元素是一致的不过set更方便统计set中是否含有某个元素。
每次学习我们都把所有课程遍历一遍如果课程我们没有学过不在set里我们就遍历这门课程的先修课程如果它的先修课程全部都在set中那么我们本轮学习就可以学这门课程把它添加进答案数组以及set中。
课程遍历完毕之后我们还需要做一个判断如果本轮学习没有学习到任何课程那么就表示我们无法学习到所有的课程图中有环返回空数组即可。
一直重复上述模拟学习的过程直到答案数组的长度等于课程数目了就表示我们学习完了所有的课程这时退出循环返回答案数组即可。 代码
class Solution {
public:unordered_mapint,vectorintm;vectorint findOrder(int numCourses, vectorvectorint prerequisites) {for(auto p:prerequisites){ //构建有向图 if(m.find(p[0])m.end()) m[p[0]]vectorint(0);m[p[0]].push_back(p[1]);}vectorintres; unordered_setints; //用于统计已经学习的课程int last0; //记录上一轮的学习课程数while(res.size()!numCourses){for(int i0;inumCourses;i){ //遍历所有课程 if(s.count(i)0){ //如果没学过课程那么进入判断bool flagtrue;for(int c:m[i]){ if(s.count(c)0){flagfalse;break;}}if(flag){ //如果本课程的所有先修课都学过,那么添加进答案res.push_back(i);s.insert(i);}}}//如果本轮学习过后,学习课程和上一轮一样,那么我们无法学完所有课程,返回空if(lastres.size()) return vectorint(0);lastres.size();}return res;}
};
