leetcode 207. Course Schedule | 207. 课程表（Java）

一时失言乱红尘 2022-10-05 12:57 111阅读 0赞

## 题目 ##

[https://leetcode.com/problems/course-schedule/][https_leetcode.com_problems_course-schedule]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

这的道题思路，来源于数据结构中的 **拓扑排序** 问题，主要思路是，通过逐步遍历删除入度为 0 的节点，判断该图是否一个有向无环图（DAG）。即，判断该图是否满足两个条件：

1.  必须能够连通所有节点 （分析本题场景发现，可以不经过所有节点）
2.  不能有环

详细解题思路见下图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]

import java.util.ArrayList;
    
    class Node { 
        int inDegree;
        ArrayList<Integer> children;
        boolean alive; // whether deleted
    
        public Node() { 
            alive = true;
            children = new ArrayList<>();
        }
    }
    
    class Solution { 
        public boolean canFinish(int numCourses, int[][] prerequisites) { 
            // init courses
            Node[] nodes = new Node[numCourses];
            for (int i = 0; i < numCourses; i++) { 
                nodes[i] = new Node();
            }
            // init prerequisites
            for (int i = 0; i < prerequisites.length; i++) { 
                nodes[prerequisites[i][0]].children.add(prerequisites[i][1]);
                nodes[prerequisites[i][1]].inDegree++;
            }
            // check DAG
            int remain = numCourses; // remaining nodes
            boolean valid = true; // last loop really works
            while (valid && remain > 0) { 
                valid = false;
                for (int i = 0; i < numCourses; i++) { 
                    if (nodes[i].inDegree == 0 && nodes[i].alive) { 
                        for (int n : nodes[i].children) {  // update
                            nodes[n].inDegree--;
                        }
                        valid = true;
                        nodes[i].alive = false;
                        remain--;
                    }
                }
            }
            return remain == 0;
        }
    }

每一次提交运行时间不一样，但总体来看效率比较低，后续看一下是否有优化解法。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]

[https_leetcode.com_problems_course-schedule]: https://leetcode.com/problems/course-schedule/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20221005/ce7d44ec7af14e4db5487aea2fffb399.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20221005/76c89cd1dcfa4aeeb690dc0cadfa854c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]: /images/20221005/20fb8367240a4787aeb40ab11124bafa.png