Leetcode刷题笔记--Hot61-70

1--课程表（207）

主要思路：

        用 in 记录每一门课程剩余的先修课程个数，当剩余先修课程个数为0时，将该课程加入到队列q中。

        每修队列q中的课程，以该课程作为先修课程的所有课程，其剩余先修课程个数减1；

        不断将剩余先修课程数为0的课程加入到队列q中，当队列为空时，若修的课程数等于总课程数，则返回true，否则返回false；

#include <iostream>
#include <vector>
#include <queue>class Solution {
public:bool canFinish(int numCourses, std::vector<std::vector<int>>& prerequisites) {std::vector<std::vector<int>> out; // 存储每一个先修课程对应的课程std::vector<int> in; // 存储每一个课程对应的剩余先修课程的个数std::queue<int> q; // 存储可以修的课程out.resize(numCourses);in.resize(numCourses);// 初始化for(auto pair : prerequisites){int cur = pair[0]; // 当前课程int pre = pair[1]; // 当前课程的先修课程out[pre].push_back(cur); // 初始化outin[cur]++;}// 选取可以直接修的课程加入到队列q中for(int i = 0; i < numCourses; i++){if(in[i] == 0) q.push(i);}int num = 0; // 已经修过的课程数while(!q.empty()){int tmp = q.front(); // 修弹出的课程q.pop();num++;// 以tmp作为先修课程的课程，其剩余的先修课程数减1for(auto course : out[tmp]){in[course] --;if(in[course] == 0) q.push(course); // course没有需要先修的课程了，因此可以加入到队列q中}}if(num == numCourses) return true;else return false;}
};int main(int argc, char* argv[]){// numCourses = 2, prerequisites = [[1,0],[0,1]]std::vector<std::vector<int>> test = {{1, 0}, {0, 1}};int numCourses = 2;Solution S1;bool res = S1.canFinish(numCourses, test);if(res) std::cout << "true" << std::endl;else std::cout << "false" << std::endl;return 0;
}

2--