Leetcode面试经典150题-210.课程表II

这个题是图的问题，因为图的拓扑排序在实际应用中有非常多的用途图，所以最近考的越来越多

解法都在代码里，不懂就留言或者私信

看这个题之前一定要好好看看207题我写的题解，也许207看懂了的话，210只是一个coding问题了

Leetcode面试经典150题-207.课程表-CSDN博客

一定要看!一定要看！一定要看！

class Solution {
    /**其实这个题一看就是第207题课程表的复杂版本，那么这个题和那个题有什么明显的不同呢，
    不同就是那个题问的是能不能完成，而这个题问的是按什么顺序完成，其实原理都是一样的
    我们只需要把过程中弹出的入度为0的课程依次记录到数组里就行*/
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        /**如果只有一个课程，拿这个课程当然能完成，他的编号为0*/
        if(numCourses == 1) {
            return new int[]{0};
        }
        /**如果大于一个课程的话我们还是按照解207题的方法，先包装一个课程类出来，然后把课程表里的入度为0的先弹出*/
        /**先定义一个hashMap用来把所有有依赖关系的课程及其依赖初始化一下，没在hashMap里的就是不依赖其他的都是可以完成的
        key是课程编号，value是真正的课程，我们初始化的过程中会把他依赖多少门课以及哪些具体的课程依赖他都确定了*/
        Map<Integer, Course> map = new HashMap<>();
        for(int[] prerequisite : prerequisites) {
            /**prerequisite是一条具体的依赖关系，prerequisite[0]依赖于prerequisite[1]*/
            /**依赖者、被依赖者如果还没有创建Course对象就先创建，因为我们后面的操作都是以Course来的 */
            if(!map.containsKey(prerequisite[0])) {
                Course course = new Course(prerequisite[0]);
                map.put(prerequisite[0], course);
            }
            if(!map.containsKey(prerequisite[1])) {
                Course course = new Course(prerequisite[1]);
                map.put(prerequisite[1], course);
            }
            /**两个课程都有了，我们就可以初始化他们之间的关系了，对于依赖别人的记录一下他到底依赖了多少课程，也就是它的入度*/
            map.get(prerequisite[0]).inDegree ++;
            /**被别人依赖的课程的next增加依赖者*/
            map.get(prerequisite[1]).nexts.add(map.get(prerequisite[0]));
        }
        /**定义结果数组*/
        int[] ans = new int[numCourses];
        /**当前有效长度以及下个要填的位置 */
        int curLen = 0;
        /**遍历一下0~numCourses-1,把没有依赖关系的先放到结果指定位置*/
        for(int i = 0; i < numCourses; i++) {
            if(!map.containsKey(i)) {
                ans[curLen ++] = i;
            }
        }
        /**队列里全是入度为0的 */
        Queue<Course> zeroInQueue = new LinkedList<>();
        /**用一个遍历count记录多少个记录入过队列 */
        int count = 0;
        /**遍历hashMap把入队为0的入队*/
        for(Course course : map.values()) {
            if(course.inDegree == 0) {
                zeroInQueue.offer(course);
            }
        }
        /**弹出队列中的课程，并在弹出时加入答案，同时减少依赖的入度*/
        while(!zeroInQueue.isEmpty()) {
            Course course = zeroInQueue.poll();
            /**课程编号加入结果 */
            ans[curLen ++] = course.courseNo;
            count ++;
            /**把依赖它的课程拿出并把这些依赖性的课程的入队-1*/
            for(Course next : course.nexts) {
                next.inDegree --;
                /**如果就依赖当前课程，那减完就是0了，也符合入队为0的条件 */
                if(next.inDegree == 0) {
                    /**注意我们是在弹出的时候加入结果，这里别加 */
                    zeroInQueue.offer(next);
                }
            }
        }
        /**如果所有的在hashmap中的课程都入过zeroInQueue，说明他们都能完成，返回ans即可，否则整个完不成返回空数组 */
        return count == map.size()? ans : new int[]{};
    }

    static class Course {
        int courseNo;
        int inDegree;
        List<Course> nexts;
        public Course(int courseNo) {
            this.courseNo = courseNo;
            this.nexts = new ArrayList<>();
        }
    }
}

结果一般，因为我利用的数据结构太多了，可以自己考虑改成数组或者别的来代替，我这边着急刷，先不优化了，毕竟面试没几个人管你的常数时间