4 - BFS & Topological Algorithm
2024-10-19 10:15:40
615. Course Schedule
https://www.lintcode.com/problem/course-schedule/description?_from=ladder&&fromId=1
为什么不可以用 for(int[] prerequisite: prerequisites) 呢 （使用Leetcode上的方法）？因为当 prerequisites 的 length 很大的时候，会超时。所以要定义一个edges[]变量，用来记录每一门课程的后续课程。
要注意数据类型的转换：
int pointer = (int)edges[curr].get(i);
indegree[pointer]--;
public class Solution {
/*
* @param numCourses: a total of n courses
* @param prerequisites: a list of prerequisite pairs
* @return: true if can finish all courses or false
*/
public boolean canFinish(int numCourses, int[][] prerequisites) {
// write your code here
if(prerequisites == null || prerequisites.length == 0 || prerequisites[0].length == 0) {
return true;
}
List[] edges = new List[numCourses];
int[] indegree = new int[numCourses];
int count = 0;
Queue<Integer> queue = new LinkedList<>();
for(int i = 0; i < numCourses; i++) {
edges[i] = new LinkedList<>();
}
int len = prerequisites.length;
for(int i = 0; i < len; i++) {
indegree[prerequisites[i][0]]++;
edges[prerequisites[i][1]].add(prerequisites[i][0]);
}
for(int i = 0; i < numCourses; i++) {
if(indegree[i] == 0) {
queue.offer(i);
}
}
while(!queue.isEmpty()) {
int curr = queue.poll();
count++;
int n = edges[curr].size();
for(int i = 0; i < n; i++) {
int pointer = (int)edges[curr].get(i);
indegree[pointer]--;
if(indegree[pointer] == 0) {
queue.offer(pointer);
}
}
}
return count == numCourses;
}
}
616. Course Schedule II
https://www.lintcode.com/problem/course-schedule-ii/description?_from=ladder&&fromId=1
public class Solution {
/*
* @param numCourses: a total of n courses
* @param prerequisites: a list of prerequisite pairs
* @return: the course order
*/
public int[] findOrder(int numCourses, int[][] prerequisites) {
// write your code here
int[] result = new int[numCourses];
List[] edges = new List[numCourses];
int[] indegree = new int[numCourses];
int count = 0;
Queue<Integer> queue = new LinkedList<>();
for(int i = 0; i < numCourses; i++) {
edges[i] = new LinkedList<>();
}
int len = prerequisites.length;
for(int i = 0; i < len; i++) {
indegree[prerequisites[i][0]]++;
edges[prerequisites[i][1]].add(prerequisites[i][0]);
}
for(int i = 0; i < numCourses; i++) {
if(indegree[i] == 0) {
queue.offer(i);
}
}
while(!queue.isEmpty()) {
int curr = queue.poll();
result[count] = curr;
count++;
int n = edges[curr].size();
for(int i = 0; i < n; i++) {
int pointer = (int)edges[curr].get(i);
indegree[pointer]--;
if(indegree[pointer] == 0) {
queue.offer(pointer);
}
}
}
if(count != numCourses) {
return new int[0];
}
return result;
}
}
最新文章
- JavaScript学习笔记(一)——延迟对象、跨域、模板引擎、弹出层、AJAX示例
- VLC 资料整理
- [转]别再抱怨了，国内这么多优秀的Android资源你都知道吗？
- 使用CallableStatement的用法
- scrapy的scrapyd使用方法
- Java EE 编程中路径
- 非Unicode工程读取Unicode文件
- js注意
- hdu----(1257)最少拦截系统（dp/LIS）
- C# 动态创建出来的窗体间的通讯 delegate2
- Qt持久性对象进行序列化（同时比较了MFC与Java的方法）
- Python-数据类型之列表
- 使用Java创建指定大小的空文件夹
- python面向对象学习（七）单例
- Linker Scripts3--MEMORY Command
- Oracle 网络监听配置管理
- Fruit Ninja（随机数rand()）
- 使用光盘作为yum软件安装源安装X Window
- 一个非常适合IT团队的在线API文档、技术文档工具 （ShowDoc）
- 《Python》 文件操作