三刷
Version #1 Topological Sort 05/2022
Time O(V + E)
Space O(V + E)
Runtime: 8 ms, faster than 61.43% of Java online submissions for Course Schedule II.
Memory Usage: 49.3 MB, less than 47.01% of Java online submissions for Course Schedule II.
class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
// prerequisites[i] = [ai, bi]
// bi -> ai
List<List<Integer>> graph = new ArrayList<>();
int[] inDegree = new int[numCourses];
for (int i = 0; i < numCourses; i++) {
graph.add(new ArrayList<>());
}
for (int[] prerequisite : prerequisites) {
int from = prerequisite[1];
int to = prerequisite[0];
inDegree[to]++;
graph.get(from).add(to);
}
int[] order = new int[numCourses];
int index = 0;
Queue<Integer> que = new ArrayDeque<>();
for (int i = 0; i < inDegree.length; i++) {
if (inDegree[i] == 0) {
que.offer(i);
}
}
while (!que.isEmpty()) {
Integer course = que.poll();
order[index++] = course;
for (Integer next : graph.get(course)) {
inDegree[next]--;
if (inDegree[next] == 0) {
que.offer(next);
}
}
}
if (index == numCourses) {
return order;
}
return new int[0];
}
}
二刷
感觉慢主要慢在HashMap<Integer, List<Integer>> 和lambda上
因为已知numCourses所以可以用array来代替HashMap和HashSet
4.98 %
class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
Map<Integer, List<Integer>> map = new HashMap<>(); // map of list of next nodes
for (int[] pre : prerequisites) {
// pre[0] curr, pre[1] prev
map.computeIfAbsent(pre[1], list -> new ArrayList<>()).add(pre[0]);
}
Stack<Integer> stack = new Stack<>();
Set<Integer> visited = new HashSet<>(); // if this course has been visited globally
for (int i = 0; i < numCourses; i++) {
// TODO
if (!dfs(i, map, new HashSet<>(), visited, stack)) {
return new int[0];
}
}
int[] result = new int[stack.size()];
int i = 0;
while (!stack.isEmpty()) {
result[i++] = stack.pop();
}
return result;
}
private boolean dfs(Integer curr, Map<Integer, List<Integer>> map, Set<Integer> path, Set<Integer> visited, Stack<Integer> stack) {
if (path.contains(curr)) {
return false;
}
if (visited.contains(curr)) {
return true;
}
path.add(curr);
visited.add(curr);
List<Integer> nexts = map.get(curr);
if (nexts != null) {
for(int next : nexts) {
if (!dfs(next, map, path, visited, stack)) {
return false;
}
}
}
stack.add(curr);
path.remove(curr);
return true;
}
}
一刷
4.65 %
public class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
if (prerequisites == null) return new int[0];
Stack<Integer> order = new Stack<>();
//index-course, value-next courses to take
boolean[][] graph = buildGraph(numCourses, prerequisites);
//TODO
Set<Integer> visited = new HashSet<>();
Boolean[] finishMem = new Boolean[numCourses];
for (int i = 0; i < numCourses; i++) {
if (!canFinish(i, graph, visited, finishMem, order)) return new int[0];
}
int[] result = new int[numCourses];
int index = 0;
while (!order.isEmpty()) {
result[index++] = order.pop();
}
return result;
}
private boolean canFinish(Integer course, boolean[][] graph, Set<Integer> visited, Boolean[] finishMem, Stack<Integer> order) {
// Starting from current course, we want to make sure that there isn't any cycles
if (finishMem[course] != null) return finishMem[course];
if (visited.contains(course)) {
finishMem[course] = false;
return false;
}
visited.add(course);
boolean currCanFinish = true;
for (int neighbor = 0; neighbor < graph[course].length; neighbor++) {
if (graph[course][neighbor] && !canFinish(neighbor, graph, visited, finishMem, order)) {
currCanFinish = false;
break;
}
}
visited.remove(course);
order.push(course);
finishMem[course] = currCanFinish;
return currCanFinish;
}
private boolean[][] buildGraph(int numCourses, int[][] prerequisites) {
boolean[][] graph = new boolean[numCourses][numCourses];
//row->course, col->next neighbors to take
for (int[] prerequisite : prerequisites) {
//pre[0] is curr, pre[1] is pre
//pre[1] -> pre[0] in graph
graph[prerequisite[1]][prerequisite[0]] = true;
}
return graph;
}
}
Version #1 BFS with Indegree
92.12 %
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
List[] edges = new ArrayList[numCourses];
int[] degree = new int[numCourses];
for (int i = 0;i < numCourses; i++)
edges[i] = new ArrayList<Integer>();
for (int i = 0; i < prerequisites.length; i++) {
degree[prerequisites[i][0]] ++ ;
edges[prerequisites[i][1]].add(prerequisites[i][0]);
}
Queue queue = new LinkedList();
for(int i = 0; i < degree.length; i++){
if (degree[i] == 0) {
queue.add(i);
}
}
int count = 0;
int[] order = new int[numCourses];
while(!queue.isEmpty()){
int course = (int)queue.poll();
order[count] = course;
count ++;
int n = edges[course].size();
for(int i = n - 1; i >= 0 ; i--){
int pointer = (int)edges[course].get(i);
degree[pointer]--;
if (degree[pointer] == 0) {
queue.add(pointer);
}
}
}
if (count == numCourses)
return order;
return new int[0];
}
}
No comments:
Post a Comment