🌕🌕 210. 课程表 II

难度: 🌕🌕

问题描述

---

解法 - bfs

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // 思路：
        // bfs 
        // bfs 每次遍历的都是当前可以修习的课程，因此按照 queue 中课程顺序添加就好
        // 其他单独的课程可随意什么时候添加
        HashSet<Integer> set = new HashSet<>();
        HashMap<Integer, ArrayList<Integer>> map = new HashMap<>();
        HashMap<Integer, Integer> freMap = new HashMap<>();
        int[] res = new int[numCourses];
        int curIndex = 0;
        for(int[] arr: prerequisites) {
            int cur = arr[0];
            int prev = arr[1];

            set.add(cur);
            set.add(prev);

            if(!map.containsKey(prev)) {
                ArrayList<Integer> tmpList = new ArrayList<>();
                map.put(prev, tmpList);
            }
            ArrayList<Integer> list = map.get(prev);
            list.add(cur);

            if(!freMap.containsKey(cur)) {
                freMap.put(cur, 1);
            } else {
                int fre = freMap.get(cur);
                fre ++;
                freMap.put(cur, fre);
            }
        }
        // 先把单独的课程先修习
        LinkedList<Integer> queue = new LinkedList<>();
        for(int i = 0; i < numCourses; i ++) {
            if(!set.contains(i)) {
                // 说明该课程是单独的
                res[curIndex] = i;
                curIndex ++;
            } else {
                // 该课程与其他课程有前置 | 后置关系
                if(!freMap.containsKey(i)) {
                    // 说明该课程无前置课程，可以修习
                    queue.offer(i);
                }
            }
        }
        // 依次修习 queue 中的课程
        while(!queue.isEmpty()) {
            int finish = queue.poll();
            res[curIndex] = finish;
            curIndex ++;
            // 修改 finish 的后置课程状态
            ArrayList<Integer> list = map.get(finish);
            if(list != null) {
                for(int next: list) {
                    int fre = freMap.get(next);
                    fre --;
                    if(fre == 0) {
                        queue.offer(next);
                    }
                    freMap.put(next, fre);
                }
            }
        }

        if(curIndex < numCourses) {
            return new int[0]; // 说明没有将所有课程加入数组中，即有的课程无法修习
        } else {
            return res;
        }
    }
}

---

输出