- class Solution {
- private:
- vector
int>> res; - void traversal(vector
int >>& graph, vector<int>& path, int s){ - path.push_back(s);
- int n=graph.size();
- if(s == n-1){
- res.push_back(path);
- }
- for(auto v:graph[s]){
- traversal(graph, path, v);
- }
- path.pop_back();
- }
- public:
- vector
int>> allPathsSourceTarget(vectorint>>& graph) { - vector<int> path;
- traversal(graph, path, 0);
- return res;
类似于多叉树
这里的s是记录正在走的节点
如果不是acyclic(无环), 要用另外一个vector 记录走过的节点,防止进入死循环
- class Solution {
- public:
- int findCelebrity(int n) {
- int cand = 0;
- for(int other = 1; other < n; other++){
- if(knows(cand, other) || !knows(other, cand)){
- cand = other;
- }
- }
-
- for(int other = 0; other
- if(cand == other) continue;
- if(knows(cand, other) || !knows(other, cand)) return -1;
- }
- return cand;
- }
- };
1.首先要排除,因为条件,所以至多有一个名人,那么两两对比,选出唯一的可能是名人的那个人
2.对比的结果有四种
3.最后剩下的那一个也不一定是名人,要在判断
207. Course Schedule
1.DFS
- class Solution {
- private:
- bool hasCycle = false;
- vector<bool> onPath;
- vector<bool> visited;
- vector
int>> buildGraph(int numCourses, vectorint>>& prerequisites){ - vector
int>> graph(numCourses); - for(auto prerequisite:prerequisites){
- int from = prerequisite[1];
- int to = prerequisite[0];
- graph[from].push_back(to);
- }
- return graph;
- }
- void traversal(vector
int >>& graph, int s){ - if(onPath[s]){
- hasCycle = true;
- }
- if(visited[s] || hasCycle){
- return;
- }
- visited[s] = true;
- onPath[s] = true;
- for(auto t:graph[s]){
- traversal(graph, t);
- }
- onPath[s] = false;
- }
- public:
- bool canFinish(int numCourses, vector
int >>& prerequisites) { - vector
int>> graph = buildGraph(numCourses, prerequisites); - visited = vector<bool>(numCourses);
- onPath = vector<bool>(numCourses);
- for(int i=0; i
- traversal(graph, i);
- }
- return !hasCycle;
- }
- };
1.首先要建一个graph表
2.遍历判断是否有环
210. Course Schedule II
- class Solution {
- private:
- vector<int> res;
- bool hasCycle;
- vector<bool> visited, onPath;
-
- void traversal(vector
int >>& graph, int s){ - if(onPath[s]){
- hasCycle = true;
- }
- if(visited[s] || hasCycle) return;
- onPath[s] = true;
- visited[s] = true;
-
- for(int t:graph[s]){
- traversal(graph, t);
- }
- res.push_back(s);
- onPath[s] = false;
- }
-
- vector
int>> buildGraph(int numCourses, vectorint>>& prerequisites){ - vector
int>> graph(numCourses); - for(auto prerequisite:prerequisites){
- int from = prerequisite[1];
- int to = prerequisite[0];
- graph[from].push_back(to);
- }
- return graph;
- }
- public:
- vector<int> findOrder(int numCourses, vector
int >>& prerequisites) { - vector
int>> graph = buildGraph(numCourses, prerequisites); - visited = vector<bool>(numCourses, false);
- onPath = vector<bool>(numCourses, false);
- for(int i=0; i
- traversal(graph, i);
- }
- if(hasCycle) return {};
- reverse(res.begin(), res.end());
- return res;
- }
- };
需要一个单独的vector记录
这里用的是后序,所以之后要reverse一下
-
相关阅读:
广度优先(BFS)(例子:迷宫)
基于kubernetes平台微服务的部署
台灯到底对眼睛好不好?2022精选眼科医生推荐护眼灯
《C Primer Plus》第12章复习题与编程练习
Android Studio实现一个垃圾分类系统(Kotlin版本)
绝对值和hashCode神奇的化学反应
【Flutter】下载安装Flutter并使用学习dart语言
基于微信小程序的知识题库系统设计与实现-计算机毕业设计源码+LW文档
第五章 延迟计算
Electron进程通信的另一种方式
-
原文地址:https://blog.csdn.net/Zoeyii/article/details/133394717