🌕🌕 207. 课程表

难度: 🌕🌕

问题描述

---

解法 1 - dfs

class Solution {
    HashSet<Integer> set;
    HashMap<Integer, ArrayList<Integer>> map;
    HashSet<Integer> finishedSet;
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 思路：
        // DFS
        // 1. 填充 set & map
        // set - 记录 数组中包含前置课程的课程，其他课程任何时候都可以修不影响
        // map = 记录 当前课程 - 修当前课程前需要修哪些课程的集合，用于 DFS 修课时判断是否成环
        // 2. 遍历 set 中所有课程
        // 3. DFS 判断 set 中每个课程是否成环，即需要修当前课程，修前置课程后发现，前置课程需要先修当前课程 的情况
        // 4. 若成环，直接返回 false; 若不成环，记录当前课程，表示该课程可以修完，继续遍历，若都不成环，返回 true
        set = new HashSet<>();
        map = new HashMap<>();
        finishedSet = new HashSet<>();
        // 1. 填充 set & map
        for(int[] arr: prerequisites) {
            int cur = arr[0];
            int prev = arr[1]; // 前置课程
            // 填充 set
            set.add(cur);
            // 填充 map
            if(!map.containsKey(cur)) {
                ArrayList<Integer> tmpList = new ArrayList<>();
                map.put(cur, tmpList);
            }
            ArrayList<Integer> list = map.get(cur);
            list.add(prev);
        }
        // 2. 遍历 set
        for(int cur : set) {
            HashSet<Integer> path = new HashSet<>();
            if(mySol(cur, path)) {
                finishedSet.add(cur);
            } else {
                return false;
            }
        }
        return true;
    }

    private boolean mySol(int cur, HashSet<Integer> path) {
        // 递归终止条件
        if(finishedSet.contains(cur)) {
            return true; // 当前课程已经验证过，不存在环，直接返回
        }
        if(!set.contains(cur)) {
            return true; // 当前课程无前置课程，可以直接修，返回
        }
        if(path.contains(cur)) {
            return false; // 当前课程要修，出现了环，无法修习，返回
        }
        path.add(cur);
        // 遍历其前置课程
        for(int prev : map.get(cur)) {
            if(!mySol(prev, path)) {
                return false; // 修前置课程过程中，成环
            }
        }
        path.remove(cur); // 回溯
        return true;
    }
}

---

输出 1

---

解法 2 - 邻接表

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 思路：
        // 邻接表 - bsf - 借助 辅助队列
        // 1. 填充 set & map
        // set - 数组中出现的所有课程，这些课程都和其他课程有关联
        // listMap - 当前课程 - 后置课程，当修完当前课程后，若后值课程就只剩下这一个前置依赖，那么也可以修了
        // freMap - 当前课程 - 还需要修多少门前置课程，才可以修习当前课程，当 == 0 时，说明可以修了
        // 2. 将 set 中无前置课程，可以直接修的课程加入 queue，表示可以修了
        // 3. 当修完无前置课程的课程后，判断它的后置课程，看有没有因为当前课程阻塞的课程，若存在，可以压入队列，进行修习
        // 4. 当 queue.isEmpty() 后，遍历 set，判断是否存在课程的前置课程 > 0 的情况，
        //   若存在，说明该课程无法修习
        HashSet<Integer> set = new HashSet<>();
        HashMap<Integer, ArrayList<Integer>> listMap = new HashMap<>();
        HashMap<Integer, Integer> freMap = new HashMap<>();
        // 1. 填充 set & map
        for(int[] arr: prerequisites) {
            int cur = arr[0];
            int prev = arr[1];
            // set
            set.add(cur);
            set.add(prev);
            // listMap
            if(!listMap.containsKey(prev)) {
                ArrayList<Integer> tmpList = new ArrayList<>();
                listMap.put(prev, tmpList);
            }
            ArrayList<Integer> list = listMap.get(prev);
            list.add(cur);
            // freMap
            if(!freMap.containsKey(cur)) {
                freMap.put(cur, 1);
            } else {
                int fre = freMap.get(cur);
                fre ++;
                freMap.put(cur, fre);
            }
        }
        // 2. 将目前无前置课程的课程加入 queue，进行修习
        LinkedList<Integer> queue = new LinkedList<>();
        for(int cur : set) {
            if(!freMap.containsKey(cur)) {
                queue.offer(cur);
            }
        }
        while(!queue.isEmpty()) {
            // 取出当前可以修习的课程
            int finish = queue.poll(); // 表示该门课程修习完成
            // 判断其后置课程，修改其 fre，若 fre == 0 加入修习队列
            ArrayList<Integer> list = listMap.get(finish);
            if(list == null) {
                continue; // 无任何后置课程，跳出当前循环，继续下一次循环
            } 
            for(int next: listMap.get(finish)) {
                int fre = freMap.get(next);
                fre --;
                if(fre == 0) {
                    queue.offer(next);
                }
                freMap.put(next, fre);
            }
        }
        // 4. 遍历 set
        for(int cur : set) {
            if(freMap.containsKey(cur) && freMap.get(cur) > 0) {
                return false;
            }
        }
        return true;
    }
}

---

输出 2