Course Schedule I & II

• 建 ArrayList[] 不能用泛型，list.get(i) 默认返回 Object，需要 cast 一下。

Course Schedule

这题的本质就是，给你一个代表 graph 的 adjacency array，判断 graph 是否有环。其实和 Graph Valid Tree 非常像。

DFS 找环性能优异，击败了 98.42 % 的提交~

public class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        ArrayList[] graph = new ArrayList[numCourses];
        int[] visited = new int[numCourses];

        for(int i = 0; i < numCourses; i++){
            graph[i] = new ArrayList<Integer>();
        }

        for(int[] num : prerequisites){
            int parent = num[1];
            int child = num[0];
            graph[parent].add(child);
        }

        for(int i = 0; i < numCourses; i++){
            if(visited[i] == 0 && hasCycle(i, visited, graph)) return false;
        }

        return true;
    }

    private boolean hasCycle(int cur, int[] visited, ArrayList[] graph){
        visited[cur] = 1;

        boolean hasCycle = false;

        for(int i = 0; i < graph[cur].size(); i++){
            int next = (int) graph[cur].get(i);
            if(visited[next] == 1) return true;
            else if(visited[next] == 0){
                hasCycle = hasCycle || hasCycle(next, visited, graph);
            }
        }

        visited[cur] = 2;

        return hasCycle;
    }
}

BFS 写法，速度超过 82.34%

思路上承接了原来的 topological sort BFS 解法，建 array 保存所有节点的 indegree，同时有数据结构存储每个节点的 children.

由于在 BFS 时只有 indegree = 0 时才会被加入队列，如果 graph 中有环，会出现有环的部分永远无法进入 BFS 被访问的情况，因此在结尾我们只需要看一下到底有没有点从来没被访问过即可。

这种情况的问题和当初面试时候问为什么 Java GC 里不只依靠 refernce counting 做的问题是一样的，就是当某个局部出现环形时，无法通过 BFS 建 reference count 的方式使所有点的当前 count = 0，因为所有点的 indegree 都非 0，无从开始。

public class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        ArrayList[] graph = new ArrayList[numCourses];
        int[] indegree = new int[numCourses];

        for(int i = 0; i < numCourses; i++){
            graph[i] = new ArrayList<Integer>();
        }

        for(int[] num : prerequisites){
            int parent = num[1];
            int child = num[0];
            graph[parent].add(child);
            indegree[child] ++; 
        }

        Queue<Integer> queue = new LinkedList<>();

        for(int i = 0; i < numCourses; i++){
            if(indegree[i] == 0) queue.offer(i);
        }

        int visitedCount = 0;

        while(!queue.isEmpty()){
            int cur = queue.poll();
            visitedCount ++;

            for(int i = 0; i < graph[cur].size(); i++){
                int next = (int) graph[cur].get(i);
                indegree[next] --;
                if(indegree[next] == 0){
                    queue.offer(next);
                }
            }
        }

        return (visitedCount == numCourses);
    }
}

Course Schedule II

超过 80.69%，速度尚可~

思路和上一题完全一样，只不过留了个 index 用于记录拓扑顺序。

public class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] rst = new int[numCourses];
        int[] indegree = new int[numCourses];
        ArrayList[] graph = new ArrayList[numCourses];

        for(int i = 0; i < numCourses; i++){
            graph[i] = new ArrayList();
        }

        for(int[] edge : prerequisites){
            int parent = edge[1];
            int child = edge[0];
            graph[parent].add(child);
            indegree[child] ++;
        }

        Queue<Integer> queue = new LinkedList<Integer>();

        for(int i = 0; i < numCourses; i++){
            if(indegree[i] == 0) queue.offer(i);
        }

        int index = 0;
        int visitedCount = 0;
        while(!queue.isEmpty()){
            int cur = queue.poll();
            rst[index ++] = cur;
            visitedCount ++;

            for(int i = 0; i < graph[cur].size(); i++){
                int next = (int) graph[cur].get(i);
                indegree[next] --;
                if(indegree[next] == 0){
                    queue.offer(next);
                }
            }
        }

        return (visitedCount == numCourses) ? rst : new int[0];
    }
}