Course Schedule ——LeetCode
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:
The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
题目大意：给一堆课程依赖，找出是否可以顺利修完全部课程，拓扑排序。
解法一：DFS+剪枝，DFS探测是否有环，图的表示采用矩阵。
public boolean canFinish(int n, int[][] p) {
if (p == null || p.length == 0) {
return true;
}
int row = p.length;
int[][] pre = new int[n][n];
for (int i = 0; i < n; i++) {
Arrays.fill(pre[i], -1);
}
for (int i = 0; i < row; i++) {
pre[p[i][0]][p[i][1]] = p[i][1];
}
// System.out.println(Arrays.deepToString(pre));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) {
continue;
}
if (pre[i][j] != -1) {
Deque<Integer> queue = new ArrayDeque<>();
queue.offer(pre[i][j]);
Set<Integer> circleDep = new HashSet<>();
circleDep.add(pre[i][j]);
while (!queue.isEmpty()) {
int dep = queue.poll();
if (dep >= row) {
continue;
}
for (int k = 0; k < n; k++) {
if (pre[dep][k] == -1) {
continue;
}
if (circleDep.contains(pre[dep][k])) {
return false;
}
queue.offer(pre[dep][k]);
circleDep.add(pre[dep][k]);
pre[dep][k]=-1;
}
}
}
}
}
return true;
}
解法二：BFS，参考别人的思路，也是用矩阵表示图，另外用indegree表示入度，先把入度为0的加入队列，当队列非空，逐个取出队列中的元素，indegree[i]-1==0的继续入队列，BFS遍历整个图，用count记录课程数，如果等于给定值则返回true。
public boolean canFinish(int n, int[][] p) {
if (p == null || p.length == 0) {
return true;
}
int[][] dep = new int[n][n];
int[] indegree = new int[n];
for(int i=0;i<p.length;i++){
if(dep[p[i][0]][p[i][1]]==1){
continue;
}
dep[p[i][0]][p[i][1]]=1;
indegree[p[i][1]]++;
}
Deque<Integer> queue = new ArrayDeque<>();
for(int i=0;i<n;i++){
if(indegree[i]==0){
queue.offer(i);
}
}
int count = 0;
while(!queue.isEmpty()){
count++;
int cos = queue.poll();
for(int i=0;i<n;i++){
if(dep[cos][i]!=0){
if(--indegree[i]==0){
queue.offer(i);
}
}
}
}
return count==n;
}
最新文章
- C# 与 SQLite的操作
- wcf测试证书的创建
- NPM安装之后CMD中不能使用
- 【Alpha版本】 第九天 11.17
- 资料共享平台----nabcd
- C#导入导出数据到Excel的通用类代码
- 关于Kingfisher--备用
- i++,++i 作为参数
- ThreadLocal(线程绑定)
- Day06（类包、内部类）
- 微信小程序外包 就找北京动软 专业承接微信小程序定制
- 计算pi的精度+进度条显示
- Gogs 部署安装(Linux)
- sqlserver 误删数据库恢复
- zoj2334 Monkey King ， 并查集，可并堆，左偏树
- 使用树莓派3获取CPU温度
- linux目录管理、时钟管理、文件查看命令
- SQL语句中 chinese_prc_CS_AI_WS 以及replace用法
- Android实例-红外线操作(XE10.2+小米5)
- ItemsSource数据源 或 集合属性 的定义 ——> 的数据源定义（典型）