网站建设推广工作描述,做网站开发app,手机网站框架,cn域名注册网站目录
题目#xff1a;
示例#xff1a;
分析#xff1a;
代码#xff1a; 题目#xff1a; 示例#xff1a; 分析#xff1a;
今天是课程表系列题目的最后一题#xff0c;因为我在题库里找不到课程表5了#xff0c;所以今天的每日一题就是最后一个课程表了。
题…目录
题目
示例
分析
代码 题目 示例 分析
今天是课程表系列题目的最后一题因为我在题库里找不到课程表5了所以今天的每日一题就是最后一个课程表了。
题目照例是给我们一堆课程的先修关系然后问我们某课程是否是另一个课程的先修课程或者是先修课程的先修课程。
如下图BCD都是A的先修课程。 把问题换个问法也就是在有向图中一个节点能否走到另一个节点。
那我们只需要递归的去寻找目标课程的先修课程直到找到对应的先修课程或者是把所有先修课程都找遍了也没找到。
DFS和BFS都可以我个人喜欢DFS所以下面代码是DFS的。
代码
class Solution {
public:unordered_mapint,vectorintm;bool find(int n,int cur,int target,unordered_setint s){if(s.count(cur)) return false; //防止重复递归同一个课程s.insert(cur);for(int i:m[cur]){ //遍历当前课程的先修课程if(itarget) return true; //如果等于了目标课程那么返回tureif(find(n,i,target,s)) return true; //再去寻找先修课程的先修课程}return false;}vectorbool checkIfPrerequisite(int numCourses, vectorvectorint prerequisites, vectorvectorint queries) {for(auto p:prerequisites){ //构建有向图if(m.find(p[0])m.end()) m[p[0]]vectorint(0);m[p[0]].push_back(p[1]);}vectorboolres;for(auto q:queries){ //遍历问题unordered_setints;if(find(numCourses,q[0],q[1],s)) res.push_back(true);else res.push_back(false);}return res;}
};
