三刷
Version #1 Topological sort with queue
Time O(E + V)
Space O(E + V)
Runtime: 7 ms, faster than 62.28% of Java online submissions for Course Schedule.
Memory Usage: 47.1 MB, less than 68.33% of Java online submissions for Course Schedule.
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
// prerequisites[i] = [ai, bi]
// bi -> ai
ArrayList<Integer>[] graph = new ArrayList[numCourses];
for (int i = 0; i < graph.length; i++) {
graph[i] = new ArrayList<>();
}
int[] inDegree = new int[numCourses];
for (int[] prerequisite : prerequisites) {
int from = prerequisite[1];
int to = prerequisite[0];
inDegree[to]++;
graph[from].add(to);
}
Queue<Integer> que = new ArrayDeque<>();
for (int i = 0; i < inDegree.length; i++) {
if (inDegree[i] == 0) {
que.offer(i);
}
}
int taken = 0;
while (!que.isEmpty()) {
Integer curr = que.poll();
taken++;
for (Integer next : graph[curr]) {
inDegree[next]--;
if (inDegree[next] == 0) {
que.offer(next);
}
}
}
return taken == numCourses;
}
}
去掉pruning以后直接TLE了。。。
看到有人的答案没有pruning也过了，大概beats 20%左右
以前以为topological sort直接就是算indegree
看了算法哥的课以后，才发现其实更直观的方法是dfs
不仅能够判断有没有环，而且能够输出sort之后的路径
如果需要路径的话，直接在end of the recursion的地方path.add(0, node)就可以了
因为一定是之后的nodes都遍历过之后，当前node才会return，所以之后的node都已经在当前node之前添加过了
二刷
69.01 %
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
// [0, 1] 1 is prerequisite of 0
List<List<Integer>> graph = buildGraph(numCourses, prerequisites);
Set<Integer> visited = new HashSet<>();
Set<Integer> path = new HashSet<>();
for (int i = 0; i < numCourses; i++) {
if (hasCycle(i, graph, visited, path)) return false;
}
return true;
}
private boolean hasCycle(int root, List<List<Integer>> graph, Set<Integer> visited, Set<Integer> path) {
if (path.contains(root)) return true;
if (visited.contains(root)) return false;
List<Integer> neighbors = graph.get(root);
path.add(root);
for (int neighbor : neighbors) {
if (hasCycle(neighbor, graph, visited, path)) {
path.remove(root);
return true;
}
}
path.remove(root);
visited.add(root);
return false;
}
private List<List<Integer>> buildGraph(int numCourses, int[][] prerequisites) {
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < numCourses; i++) {
graph.add(new ArrayList<>());
}
int start = 0;
int end = 0;
for (int[] prerequisite : prerequisites) {
graph.get(prerequisite[1]).add(prerequisite[0]);
}
return graph;
}
}
73.76 %
public class Solution {
// To check if there's any cycle
// course prerequisite
// [0, 1 ] 1 --> 0
public boolean canFinish(int numCourses, int[][] prerequisites) {
if (prerequisites == null || prerequisites.length == 0) return true;
//index-course, value-next courses to take
List<List<Integer>> graph = buildGraph(numCourses, prerequisites);
Set<Integer> visited = new HashSet<>();
Boolean[] finishMem = new Boolean[numCourses];
for (int i = 0; i < numCourses; i++) {
if (!canFinish(i, graph, visited, finishMem)) return false;
}
return true;
}
private boolean canFinish(Integer course, List<List<Integer>> graph, Set<Integer> visited, Boolean[] finishMem) {
// 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 (Integer neighbor : graph.get(course)) {
if (!canFinish(neighbor, graph, visited, finishMem)) {
currCanFinish = false;
break;
}
}
visited.remove(course);
finishMem[course] = currCanFinish;
return currCanFinish;
}
private List<List<Integer>> buildGraph(int numCourses, int[][] prerequisites) {
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < numCourses; i++) {
graph.add(new ArrayList<Integer>());
}
for (int[] prerequisite : prerequisites) {
//pre[0] is curr, pre[1] is pre
//pre[1] -> pre[0] in graph
graph.get(prerequisite[1]).add(prerequisite[0]);
}
return graph;
}
}
Version #2 Topological Sort
二刷
21.55 %
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
int[] indegree = new int[numCourses];
// to add all courses with indegrees of zero into queue -> means they don't have any prerequisite
// when we polled one course out, we finished this course and all courses whose prerequisite contains this course can do a indegree--
// if any courses indegree becomes zero, we can push it into queue
Map<Integer, List<Integer>> map = new HashMap<>();
for (int[] pre : prerequisites) {
// pre[0] -> curr, pre[1] -> pre
map.computeIfAbsent(pre[1], list -> new ArrayList<>()).add(pre[0]);
indegree[pre[0]]++;
}
Queue<Integer> que = new LinkedList<>();
for (int i = 0; i < numCourses; i++) {
if (indegree[i] == 0) {
que.offer(i);
}
}
int visited = 0;
while (!que.isEmpty()) {
int curr = que.poll();
visited++;
if (!map.containsKey(curr)) continue;
for (int next : map.get(curr)) {
if (indegree[next] > 0) {
indegree[next]--;
if (indegree[next] == 0) {
que.offer(next);
}
}
}
}
return visited == numCourses;
}
}
一刷
典型的topological sorting with in-degree
这里不用写出sorting 的顺序，只要判断有没有环
判断依据是把所有indegree为0的点加入que，记录一个visitedCount
如果最终visit点的个数和nodes个数不相等证明有环，证明把所有indegree为0的点删除后图上面还有剩余的点
71.11 %
public class Solution {
//[0,1] [curr, pre]
public boolean canFinish(int numCourses, int[][] prerequisites) {
if (prerequisites == null || prerequisites.length == 0) return true;
Integer[] indegree = new Integer[numCourses];
List<List<Integer>> graph = buildGraph(numCourses, prerequisites, indegree);
int visitedCount = 0;
Queue<Integer> que = new LinkedList<>();
for (int i = 0; i < numCourses; i++) {
if (indegree[i] == 0) que.add(i);
}
while (!que.isEmpty()) {
List<Integer> neighbors = graph.get(que.poll());
visitedCount++;
for(Integer neighbor : neighbors) {
if (--indegree[neighbor] == 0) que.add(neighbor);
}
}
return visitedCount == numCourses;
}
private List<List<Integer>> buildGraph(int numCourses, int[][] prerequisites, Integer[] indegree) {
List<List<Integer>> graph = new ArrayList<>();
//index->course number, list->its next neighbors
for (int i = 0; i < numCourses; i++) {
graph.add(new ArrayList<>());
indegree[i] = 0;
}
for (int[] prerequisite : prerequisites) {
//prerequisite[0] -> curr
//prerequisite[1] -> pre
graph.get(prerequisite[1]).add(prerequisite[0]);
indegree[prerequisite[0]] += 1;
}
return graph;
}
}
No comments:
Post a Comment