【LeetCode207.课程表】以及变式
题目链接
207. 课程表 - 力扣(LeetCode)
实现思路
- 用一个二维数组存邻接表,存储的是某个课程的下一门课程的集合;
- 用一个数组存储每门课程的入度,也就是如果某门课程需要另外一门先修课程,入度就+1;
- 用一个队列,存储当前入度为0的课程,也就是可以修的课程x,每次循环,判断x作为哪些课程的先修课程,那么这门课程的入度-1,如果为0,这门课程也可以修了,加入队列中;
- 最后,判断完成的课程数是否和总课程数相等。
代码实现
class Solution {
public:bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {// 构造邻接表vector<vector<int>> edges(numCourses);// 统计入度vector<int> indegree(numCourses, 0);for (int i = 0; i < prerequisites.size(); i++) {int x = prerequisites[i][0];int y = prerequisites[i][1];edges[x].push_back(y);indegree[y]++;}int finish = 0;queue<int> q;for (int i = 0; i < numCourses; i++) {if (!indegree[i]) {finish++;q.push(i);}}while (q.size()) {int x = q.front();q.pop();for (int y : edges[x]) {indegree[y]--;if (!indegree[y]) {finish++;q.push(y);}}}return finish == numCourses;}
};
变式
题目解析
如果已经修好的课程是通过另外一个数组传入的,也就是说,如果仅仅给出修课条件[[1,0]],那么0,1两门课都不能修,但是如果已经修好的课程数组为[0],那么0,1就都可以修。(限制:不存在循环依赖的情况,也就是0的先修课程是1,1的先修课程是0的情况)。
实现思路
- 在之前的代码上,增加一个判断,就是如果不在已经学习的集合中,那么就算通过邻接图的入度为0,也要手动将入度设置为1。
代码实现
class Solution {
public:bool canFinish(int numCourses, vector<vector<int>>& prerequisites, set<int>& learned) {// 构造邻接表vector<vector<int>> edges(numCourses);// 统计入度vector<int> indegree(numCourses, 0);for (int i = 0; i < prerequisites.size(); i++) {int x = prerequisites[i][0];int y = prerequisites[i][1];edges[x].push_back(y);indegree[y]++;}// 新增:只有在learned数组中的课程,入度才是0,否则若原来是0的需要改为1for (int i = 0; i < numCourses; i++) {if (!indegree[i] && !learned.count(i)) {indegree[i] = 1;}}int finish = 0;queue<int> q;for (int i = 0; i < numCourses; i++) {if (!indegree[i]) {finish++;q.push(i);}}while (q.size()) {int x = q.front();q.pop();for (int y : edges[x]) {indegree[y]--;if (!indegree[y]) {finish++;q.push(y);}}}return finish == numCourses;}
};