207. 课程表 (opens new window)

1.回溯+DFS

解题核心在于判断一个数列是否存在回环的问题。

• 哈希表保存所有课表，其中key为当前课程，value保存该课程的所有前置课程列表。
• 用currlist列表保存当前已搜索过的列表。需要考虑以下几种情况，同一门课程可能出现在不同分支，因此当前元素是否构成回环，不能通过currlist中是否出现过来判断。而要解决这个问题，每次当前课表元素进行搜索时进行回溯即可。这样就可以保证当前currlist中，仅保存一条分支回路出现的所有课程。

• 剪枝：visited保存前置课程不含有回路的所有节点。当前头节点在搜索每个子节点(前置课程)时，如果子节点的所有前置课程均不存在回路，用visited列表保存起来。后续在搜索其它节点时，如果该子节点再次被搜索(作为头结点)，那么此时就不需要再搜索下去了。

  例子：以上面图中的课程路径为例，4节点经过判定不含回路，那么就将该节点加入到visited中，下一次(其他分支或者是作为头结点)再遇上时，不需要再往下搜索。

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        HashMap<Integer, List<Integer>> map = new HashMap<>();
        List<Integer> currlist = new ArrayList<>();
        List<Integer> visited = new ArrayList<>();
        //存储数据
        for (int i = 0; i < prerequisites.length; i++) {
            if (map.containsKey(prerequisites[i][0])) {
                List<Integer> temp = map.get(prerequisites[i][0]);
                temp.add(prerequisites[i][1]);
            } else {
                List<Integer> temp = new ArrayList<>();
                temp.add(prerequisites[i][1]);
                map.put(prerequisites[i][0], temp);
            }
        }
        //搜索
        for (Integer temp : map.keySet()) {
            currlist.add(temp);
            if (check(map, currlist, visited, temp)) return false;
            currlist.remove(temp);
        }
        return true;
    }
    public boolean check(HashMap<Integer, List<Integer>> map, List<Integer> currlist, List<Integer> visited, int curr) {
        //剪枝
        if (!map.containsKey(curr) || visited.contains(curr)) return false;
        List<Integer> list = map.get(curr);
        for (Integer integer : list) {
            if (currlist.contains(integer)) {
                return true;
            }
            currlist.add(integer);
            if (check(map, currlist, visited, integer)) return true;
            //回溯
            currlist.remove(integer);
        }
        visited.add(curr);
        return false;
    }
}

2.拓扑排序

节点存储

先上i才能上j，那么i的出度加一，j的入度加一。

• 每次把入度为0的节点放入队列
• 队列中的每当有一个节点出列，需要改变依赖该节点的所有节点的入度。
• 把新的入度为0的节点加入队列，重复2步骤

具体使用数据结构存储如下：

1️⃣开辟数组保存每个节点的入度大小，按照每个节点的索引进行存储。

2️⃣哈希表保存每个节点的出度指向的数组，其中key为节点的索引，value保存所有依赖key的所有节点。

如何判断修完所有的课程？

初始时，将所有入度为0的节点都加入到队列当中。当BFS遍历完所有的节点，如果数组中仍然存在入度不为0的节点，那么说明该节点构成回环。

210. 课程表 II (opens new window)

1.广搜+拓扑排序

数据结构：

• output：保存图的出度信息，value为key节点的所有出度节点集合
• input：保存每个节点的入度值。当入度为0时，说明当前节点没有前置要求，可以直接修这一门课
• queue：初始化保存所有入度为0的节点值

算法流程：

1. 初始化保存图的信息以及queue队列
2. 遍历队列，将每个入度为零的节点值node出队
3. 将node加入结果集
4. 从output获取node节点的出度节点集合，更新计算出度集合所有节点的入度值；若更新后该节点入度为0，则加入队列
5. 重复②-④操作，直至队列为0

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        Map<Integer,List<Integer>> output=new HashMap<>();
        Map<Integer,Integer> input=new HashMap<>();
        for(int i=0;i<prerequisites.length;i++){
            if(output.containsKey(prerequisites[i][1])){
                List<Integer> list=output.get(prerequisites[i][1]);
                list.add(prerequisites[i][0]);
            }
            else{
                List<Integer> list=new ArrayList<>();
                list.add(prerequisites[i][0]);
                output.put(prerequisites[i][1],list);
            }
            input.put(prerequisites[i][0],input.getOrDefault(prerequisites[i][0],0)+1);
        }
        Deque<Integer> queue=new LinkedList<>();
        for(int i=0;i<numCourses;i++){
            if(!input.containsKey(i)) queue.offerLast(i);
        }
        List<Integer> res=new ArrayList<>();
        while(!queue.isEmpty()){
            int tmp = queue.pollFirst();
            if (output.containsKey(tmp)) {
                List<Integer> list = output.get(tmp);
                for (Integer integer : list) {
                    input.put(integer, input.get(integer) - 1);
                    if(input.get(integer)==0){
                        queue.offerLast(integer);
                        input.remove(integer);
                    }
                }
            }
            res.add(tmp);
        }
        if(res.size()<numCourses) return new int[0];
        return res.stream().mapToInt(Integer::valueOf).toArray();
    }
}