Course Schedule

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

207. Course Schedule

好题。三种状态，0没访问过，1正在访问，2已访问过。

用DFS找环的效率很高。

public class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] visited = new int[numCourses];
        Map<Integer, List<Integer>> graph = new HashMap<>();

        for (int[] num : prerequisites) {
            int parent = num[1];
            int child = num[0];
            if (graph.containsKey(parent)) {
                List<Integer> list = graph.get(parent);
                list.add(child);
                graph.put(parent, list);
            } else {
                List<Integer> list = new ArrayList<>();
                list.add(child);
                graph.put(parent, list);
            }
        }

        for (int i = 0; i < numCourses; ++i) {
            if (visited[i] == 0 && dfs(graph, visited, i)) return false;
        }
        return true;
    }
    private boolean dfs(Map<Integer, List<Integer>> graph, int[] visited, int cur) {
        visited[cur] = 1;

        boolean cycle = false;
        if (graph.containsKey(cur)) {
            for (int i = 0; i < graph.get(cur).size(); ++i) {
                int next = (int) graph.get(cur).get(i);
                if (visited[next] == 1) return true;
                if (visited[next] == 0) {
                    cycle = cycle || dfs(graph, visited, next);
                }
            }
        }
        visited[cur] = 2;
        return cycle;
    }
}

BFS写法思路上承接了原来的 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) {
        int[] visited = new int[numCourses];
        int[] inDegree = new int[numCourses];
        Map<Integer, List<Integer>> map = new HashMap<>();

        for (int[] sum : prerequisites) {
            int parent = sum[1];
            int child = sum[0];
            inDegree[child]++;
            if (map.containsKey(parent)) {
                List<Integer> list = map.get(parent);
                list.add(child);
                map.put(parent, list);
            } else {
                List<Integer> list = new ArrayList<>();
                list.add(child);
                map.put(parent, list);
            }
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; ++i) {
            if (inDegree[i] == 0) queue.offer(i);
        }
        int count = 0;
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            count++;
            if (map.containsKey(cur)) {
                for (int i = 0; i < map.get(cur).size(); ++i) {
                    int next = map.get(cur).get(i);
                    inDegree[next]--;
                    if (inDegree[next] == 0) queue.offer(next);
                }
            }
        }

        return count == numCourses;
    }
}

7/18更新：

这次做只用了一个degree数组解的。也AC了。

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

        for (int i = 0; i < prerequisites.length; ++i) {
            degree[prerequisites[i][0]]++;
        }
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < degree.length; ++i) {
            if (degree[i] == 0) queue.offer(i);
        }
        while (!queue.isEmpty()) {
            int course = queue.poll();
            for (int i = 0; i < prerequisites.length; ++i) {
                if (prerequisites[i][1] == course) {
                    degree[prerequisites[i][0]]--;
                    if (degree[prerequisites[i][0]] == 0) queue.offer(prerequisites[i][0]);
                }
            }
        }
        for (int i = 0; i < degree.length; ++i) {
            if (degree[i] != 0) return false;
        }
        return true;
    }
}

210. Course Schedule II

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

public class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] visited = new int[numCourses];
        Map<Integer, List<Integer>> map = new HashMap<>();
        int[] inDegree = new int[numCourses];

        for (int[] num : prerequisites) {
            int parent = num[1];
            int child = num[0];
            inDegree[child]++;
            if (map.containsKey(parent)) {
                List<Integer> list = map.get(parent);
                list.add(child);
                map.put(parent, list);
            } else {
                List<Integer> list = new ArrayList<>();
                list.add(child);
                map.put(parent, list);
            }
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; ++i) {
            if (inDegree[i] == 0) queue.offer(i);
        }
        int count = 0;
        int[] res = new int[numCourses];
        int index = 0;
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            count++;
            res[index++] = cur;

            if (map.containsKey(cur)) {
                for (int i = 0; i < map.get(cur).size(); ++i) {
                    int next = map.get(cur).get(i);
                    inDegree[next]--;
                    if (inDegree[next] == 0) queue.offer(next);
                }
            }
        }
        return (count == numCourses) ? res : new int[0];
    }
}

7/18: 顺着前面的做法

public class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] result = new int[numCourses];
        int[] degree = new int[numCourses];
        for (int i = 0; i < prerequisites.length; ++i) {
            degree[prerequisites[i][0]]++; 
        }
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < degree.length; ++i) {
            if (degree[i] == 0) queue.offer(i);
        }
        int count = 0;
        while (!queue.isEmpty()) {
            int course = queue.poll();
            result[count++] = course;
            for (int i = 0; i < prerequisites.length; ++i) {
                if (prerequisites[i][1] == course) {
                    degree[prerequisites[i][0]]--;
                    if (degree[prerequisites[i][0]] == 0) queue.offer(prerequisites[i][0]);
                }
            }
        }
        boolean flag = false;
        for (int i = 0; i < degree.length; ++i) {
            if (degree[i] != 0) flag = true;
        }
        return flag ? new int[0] : result;
    }
}