【每日一题Day321】LC207课程表 | 拓扑排序

简介: 【每日一题Day321】LC207课程表 | 拓扑排序

课程表【LC207】

你这个学期必须选修 numCourses 门课程,记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出,其中 prerequisites[i] = [ai, bi] ,表示如果要学习课程 ai 则 必须 先学习课程 bi 。

例如,先修课程对 [0, 1] 表示:想要学习课程 0 ,你需要先完成课程 1 。

请你判断是否可能完成所有课程的学习?如果可以,返回 true ;否则,返回 false 。

  • 思路
    由于在选修课程 ai必须 先选修 bi ,因此我们可以构建一条由bi 指向 ai的边,然后使用拓扑排序,优先遍历入度为0的节点,并将其加入拓扑排序数组中,如果最后数组的大小与节点个数不相同,那么证明有向图中有环存在,不可能完成所有课程
  • 实现
class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        Deque<Integer> queue = new LinkedList<>();
        int[] inDeg = new int[numCourses];
        List<Integer>[] after = new List[numCourses];
        Arrays.setAll(after, e -> new ArrayList<>());
        for (int[] pre : prerequisites){
            inDeg[pre[0]]++;
            after[pre[1]].add(pre[0]);
        }
        List<Integer> sorted = new ArrayList<>();
        for (int i = 0; i < numCourses; i++){
            if (inDeg[i] == 0){
                queue.addLast(i);
            }
        }
        while(!queue.isEmpty()){
            int x = queue.pollFirst();
            sorted.add(x);
            for (int y : after[x]){
                inDeg[y]--;
                if (inDeg[y] == 0){
                    queue.addLast(y);
                }
            }
        }
        return sorted.size() == numCourses;
    }
}

复杂度


时间复杂度:O ( E + V ),E表示邻边的跳数,V为结点的个数

空间复杂度:O ( V )

目录
相关文章
|
6月前
【每日一题Day366】LC2103环和杆 | 状态压缩
【每日一题Day366】LC2103环和杆 | 状态压缩
48 0
|
6月前
|
存储
【每日一题Day275】LC771宝石与石头 | 哈希表 状态压缩
【每日一题Day275】LC771宝石与石头 | 哈希表 状态压缩
43 0
|
6月前
|
定位技术
【每日一题Day200】LC1263推箱子 | 01-BFS
【每日一题Day200】LC1263推箱子 | 01-BFS
41 1
|
6月前
|
人工智能 BI
【每日一题Day322】LC210课程表 II | 拓扑排序
【每日一题Day322】LC210课程表 II | 拓扑排序
34 0
|
6月前
|
机器学习/深度学习 存储
【每日一题Day323】LC630课程表 III | 动态规划 反悔贪心
【每日一题Day323】LC630课程表 III | 动态规划 反悔贪心
42 0
|
6月前
|
人工智能 BI
【每日一题Day324】LC1462课程表 IV | BFS 拓扑排序 Floyd
【每日一题Day324】LC1462课程表 IV | BFS 拓扑排序 Floyd
30 0
|
6月前
【每日一题Day279】LC2050并行课程 III | 拓扑排序
【每日一题Day279】LC2050并行课程 III | 拓扑排序
50 0
|
6月前
【每日一题Day329】LC213打家劫舍Ⅱ | 动态规划
【每日一题Day329】LC213打家劫舍Ⅱ | 动态规划
38 0
|
6月前
【每日一题Day330】LC337打家劫舍Ⅲ | 动态规划
【每日一题Day330】LC337打家劫舍Ⅲ | 动态规划
35 0
|
6月前
【每日一题Day328】LC198打家劫舍 | 动态规划
【每日一题Day328】LC198打家劫舍 | 动态规划
52 0