Course Schedule题解
原创文章,拒绝转载
题目来源:https://leetcode.com/problems/course-schedule/description/
Description
There are a total of n courses you have to take, labeled from 0 to n - 1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
For example:
2, [[1,0]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.
2, [[1,0],[0,1]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.
Note:
1. The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
2. You may assume that there are no duplicate edges in the input prerequisites.
Solution
class Solution {
private:
bool **graph;
int* color;
int graphDim = 0;
public:
~Solution() {
if (graphDim == 0)
return;
delete[] color;
for (int i = 0; i < graphDim; i++)
delete[] graph[i];
delete graph;
}
bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
if (numCourses <= 0)
return false;
if (prerequisites.size() == 0)
return true;
int i, j;
graphDim = numCourses;
graph = new bool*[numCourses];
color = new int[numCourses];
for (i = 0; i < numCourses; i++)
graph[i] = new bool[numCourses];
for (i = 0; i < numCourses; i++) {
color[i] = 0;
for (j = 0; j < numCourses; j++) {
graph[i][j] = false;
}
}
for (auto p: prerequisites) {
graph[p.first][p.second] = true;
}
int sv;
for (auto p: prerequisites) {
sv = p.first;
for (i = 0; i < numCourses; i++) {
if (graph[sv][i]) {
if (color[sv] == 2)
continue;
if (!dfs(sv))
return false;
else
color[i] = 2;
}
}
}
return true;
}
bool dfs(int v) {
color[v] = 1;
int i;
for (i = 0; i < graphDim; i++) {
if (graph[v][i]) {
if (color[i] == 2) {
break;
} else if (color[i] == 1) {
return false;
} else {
if (!dfs(i)) {
return false;
}
}
}
}
color[v] = 2;
return true;
}
};
解题描述
这道题我使用的是DFS,过程中通过对以访问的顶点进行染色来判断是否有环。不过提交后出现了几次TLE,检查代码发现好几处可以充分利用染色数组来减少充分访问。改了好几次才AC。现实利用中DFS和BFS处理的数据量往往会很大,这几次TLE还是提醒我要注意优化算法时间复杂度。
文章更新
这道题本质上是检查图是否有环,而如果图是可以拓扑排序的,则一定是无环的。通过BFS检查图是否能够拓扑排序也是可以解决的,且相对来说实现效率较高,避免了DFS的递归开销。下面给出实现:
class Solution
{
private:
map<int, int> inDegree;
public:
bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
int i, curVertex;
for (i = 0; i < numCourses; i++)
inDegree[i] = 0;
for (auto p: prerequisites)
inDegree[p.second]++;
queue<int> vq;
for (i = 0; i < numCourses; i++) {
if (inDegree[i] == 0) {
vq.push(i);
}
}
if (vq.empty())
return false;
while (!vq.empty()) {
curVertex = vq.front();
vq.pop();
inDegree.erase(curVertex);
for (i = 0; i < prerequisites.size(); i++) {
if (curVertex == prerequisites[i].first) {
inDegree[prerequisites[i].second]--;
if (inDegree[prerequisites[i].second] == 0)
vq.push(prerequisites[i].second);
}
}
}
return inDegree.empty();
}
};
[Leetcode Week3]Course Schedule的更多相关文章
-
Java for LeetCode 210 Course Schedule II
There are a total of n courses you have to take, labeled from 0 to n - 1. Some courses may have prer ...
-
Java for LeetCode 207 Course Schedule【Medium】
There are a total of n courses you have to take, labeled from 0 to n - 1. Some courses may have prer ...
-
LeetCode 210. Course Schedule II(拓扑排序-求有向图中是否存在环)
和LeetCode 207. Course Schedule(拓扑排序-求有向图中是否存在环)类似. 注意到.在for (auto p: prerequistites)中特判了输入中可能出现的平行边或 ...
-
[LeetCode] 207. Course Schedule 课程安排
There are a total of n courses you have to take, labeled from 0 to n - 1. Some courses may have prer ...
-
[Leetcode Week4]Course Schedule II
Course Schedule II题解 原创文章,拒绝转载 题目来源:https://leetcode.com/problems/course-schedule-ii/description/ De ...
-
[LeetCode] 210. Course Schedule II 课程清单之二
There are a total of n courses you have to take, labeled from 0 to n-1. Some courses may have prereq ...
-
[LeetCode] 207. Course Schedule 课程清单
There are a total of n courses you have to take, labeled from 0 to n-1. Some courses may have prereq ...
-
LeetCode - 207. Course Schedule
207. Course Schedule Problem's Link ---------------------------------------------------------------- ...
-
Leetcode 210 Course Schedule II
here are a total of n courses you have to take, labeled from 0 to n - 1. Some courses may have prere ...
随机推荐
-
Webservice简介
一.序言 大家或多或少都听过WebService(Web服务),有一段时间很多计算机期刊.书籍和网站都大肆的提及和宣传WebService技术,其中不乏很多吹嘘和做广告的成分.但是不得不承认的是Web ...
-
Azure China (7) 使用WebMetrix将Web Site发布至Azure China
<Windows Azure Platform 系列文章目录> 本章介绍的是,使用世纪互联运维的Azure云服务. 1.首先我们登陆Azure管理界面.http://manage.wind ...
-
JAVA的覆盖、继承和多态的详细解说.this和super的用法
1. 继承: (1)子类的构造方法一定会调用父类的构造方法. (2)任何子类构造方法第一行肯定是this();或者super();两个择一. this();调用本类的其它构造方法.(传递相应参数调用相 ...
-
c 函数及指针学习 7
1.结构的存储分配 1 2 printf("%d \n",sizeof(char)); printf("%d \n",sizeof(int)); int 类型为 ...
-
hdu 2028 Lowest Common Multiple Plus(最小公倍数)
Lowest Common Multiple Plus Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (J ...
-
iOS开发怎么样做第三方登陆(友盟社会化分享)
基于前一篇文章 自定义UI后 实现如下代码 即可 //第三方登陆 // UMSocialSnsPlatform *snsPlatform = [UMSocialSnsPlatformMa ...
-
Python 学习笔记8
在最想放弃的时候 想想美好的事情 想想明天. 今天继续看错误与异常. http://www.pythondoc.com/pythontutorial3/errors.html
-
解决Perhaps you are running on a JRE rather than a JDK?问题
Maven-No compiler is provided in this environment. Perhaps you are running on a JRE rather than a JD ...
-
git status 显示中文乱码
场景 在使用git命令行查看当前 状态时, git status 显示中文文件乱码: 解决 修改git配置, git config --global core.quotepath false
-
UVALive - 3523 - Knights of the Round Table
Problem UVALive - 3523 - Knights of the Round Table Time Limit: 4500 mSec Problem Description Input ...