【LeetCode: 210. 课程表 II:拓扑排序+图】

这篇具有很好参考价值的文章主要介绍了【LeetCode: 210. 课程表 II:拓扑排序+图】。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【LeetCode: 210. 课程表 II:拓扑排序+图】,LeetCode每日一题打卡,leetcode,算法,java,拓扑排序,图论,面试

🚀 算法题 🚀

🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀
🌲 越难的东西,越要努力坚持,因为它具有很高的价值,算法就是这样✨
🌲 作者简介:硕风和炜,CSDN-Java领域优质创作者🏆,保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享💎💎💎
🌲 恭喜你发现一枚宝藏博主,赶快收入囊中吧🌻
🌲 人生如棋,我愿为卒,行动虽慢,可谁曾见我后退一步?🎯🎯

🚀 算法题 🚀

【LeetCode: 210. 课程表 II:拓扑排序+图】,LeetCode每日一题打卡,leetcode,算法,java,拓扑排序,图论,面试

🚩 题目链接

  • 210. 课程表 II

⛲ 题目描述

现在你总共有 numCourses 门课需要选,记为 0 到 numCourses - 1。给你一个数组 prerequisites ,其中 prerequisites[i] = [ai, bi] ,表示在选修课程 ai 前 必须 先选修 bi 。

例如,想要学习课程 0 ,你需要先完成课程 1 ,我们用一个匹配来表示:[0,1] 。
返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序,你只要返回 任意一种 就可以了。如果不可能完成所有课程,返回 一个空数组 。

示例 1:

输入:numCourses = 2, prerequisites = [[1,0]]
输出:[0,1]
解释:总共有 2 门课程。要学习课程 1,你需要先完成课程 0。因此,正确的课程顺序为 [0,1] 。
示例 2:

输入:numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
输出:[0,2,1,3]
解释:总共有 4 门课程。要学习课程 3,你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
因此,一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。
示例 3:

输入:numCourses = 1, prerequisites = []
输出:[0]

提示:
1 <= numCourses <= 2000
0 <= prerequisites.length <= numCourses * (numCourses - 1)
prerequisites[i].length == 2
0 <= ai, bi < numCourses
ai != bi
所有[ai, bi] 互不相同

🌟 求解思路&实现代码&运行结果


⚡ 图+拓扑排序

🥦 求解思路
  1. 首先在求解这道题目之前,可以先来学习一下昨天的题目,课程表1,207. 课程表
    ,博客链接地址放到这里了,需要的同学可以直接跳转,课程表1博客地址,这道题目是上一道题目的变种,总体的求解思路是一样的,只需要求出拓扑排序的一种顺序即可。
  2. 有了基本的思路,接下来我们就来通过代码来实现一下。
🥦 实现代码
class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int m=prerequisites.length;
        if(numCourses==0||prerequisites==null) return new int[]{};
        int[] degree=new int[numCourses];
        ArrayList<Integer>[] list=new ArrayList[numCourses];
        Arrays.setAll(list,e->new ArrayList<>());
        Queue<Integer> queue=new LinkedList<>();
        for(int i=0;i<m;i++){
            int[] temp=prerequisites[i];
            int from=temp[1],to=temp[0];
            list[from].add(to);
            degree[to]++;
        }
        for(int i=0;i<numCourses;i++){
            if(degree[i]==0){
                queue.add(i);
            }
        }
        int[] ans=new int[numCourses];
        int cnt=0;
        while(!queue.isEmpty()){
            int next=queue.poll();
            ans[cnt++]=next;
            for(int v:list[next]){
                if(--degree[v]==0){
                    queue.add(v);
                }
            }
        }
        return cnt==numCourses?ans:new int[]{};
    }
}
🥦 运行结果

时间复杂度&空间复杂度

【LeetCode: 210. 课程表 II:拓扑排序+图】,LeetCode每日一题打卡,leetcode,算法,java,拓扑排序,图论,面试


💬 共勉

最后,我想和大家分享一句一直激励我的座右铭,希望可以与大家共勉!

【LeetCode: 210. 课程表 II:拓扑排序+图】,LeetCode每日一题打卡,leetcode,算法,java,拓扑排序,图论,面试

【LeetCode: 210. 课程表 II:拓扑排序+图】,LeetCode每日一题打卡,leetcode,算法,java,拓扑排序,图论,面试文章来源地址https://www.toymoban.com/news/detail-704004.html

到了这里,关于【LeetCode: 210. 课程表 II:拓扑排序+图】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【力扣热题100】207. 课程表 python 拓扑排序

    刷一道力扣热题100吧 难度中等 https://leetcode.cn/problems/course-schedule/?envType=study-plan-v2envId=top-100-liked 你这个学期必须选修 numCourses 门课程,记为 0 到 numCourses - 1 。 在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出,其中 prerequisites[i] = [ai, bi] ,表示如果要

    2024年02月04日
    浏览(45)
  • 2023-09-09 LeetCode每日一题(课程表)

    点击跳转到题目位置 你这个学期必须选修 numCourses 门课程,记为 0 到 numCourses - 1 。 在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出,其中 prerequisites[i] = [ai, bi] ,表示如果要学习课程 ai 则 必须 先学习课程 bi 。 例如,先修课程对 [0, 1] 表示:想要学

    2024年02月09日
    浏览(53)
  • 2023-09-11 LeetCode每日一题(课程表 III)

    点击跳转到题目位置 这里有 n 门不同的在线课程,按从 1 到 n 编号。给你一个数组 courses ,其中 courses[i] = [durationi, lastDayi] 表示第 i 门课将会 持续 上 durationi 天课,并且必须在不晚于 lastDayi 的时候完成。 你的学期从第 1 天开始。且不能同时修读两门及两门以上的课程。 返

    2024年02月09日
    浏览(40)
  • java实现课程表 II

    题目: 现在你总共有  numCourses  门课需要选,记为  0  到  numCourses - 1 。给你一个数组  prerequisites  ,其中  prerequisites[i] = [ai, bi]  ,表示在选修课程  ai  前  必须  先选修  bi  。 例如,想要学习课程  0  ,你需要先完成课程  1  ,我们用一个匹配来表示: [0,1]  。

    2024年02月09日
    浏览(45)
  • 想要精通算法和SQL的成长之路 - 课程表II

    想要精通算法和SQL的成长之路 - 系列导航 原题链接 核心知识: 拓扑排序是专门 应用于有向图的算法。 BFS 的写法就叫拓扑排序,核心就是: 让入度为0的节点入队。 拓扑排序的 结果不唯一。 同时拓扑排序有一个重要的功能: 能够检测有向图中是否存在环。 我们先分析一下

    2024年02月09日
    浏览(35)
  • leetcode207. 课程表

    你这个学期必须选修 numCourses 门课程,记为 0 到 numCourses - 1 。 在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出,其中 prerequisites[i] = [ai, bi] ,表示如果要学习课程 ai 则 必须 先学习课程 bi 。 例如,先修课程对 [0, 1] 表示:想要学习课程 0 ,你需要先

    2023年04月24日
    浏览(44)
  • leetcode 630. 课程表 III

    这里有 n 门不同的在线课程,按从 1 到 n 编号。给你一个数组 courses ,其中 courses[i] = [durationi, lastDayi] 表示第 i 门课将会 持续 上 durationi 天课,并且必须在不晚于 lastDayi 的时候完成。 你的学期从第 1 天开始。且不能同时修读两门及两门以上的课程。 返回你最多可以修读的课

    2024年02月16日
    浏览(43)
  • 【图论】Leetcode 207. 课程表【中等】

    你这个学期必须选修 numCourses 门课程,记为 0 到 numCourses - 1 。 在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出,其中 prerequisites[i] = [ai, bi] ,表示如果要学习课程 ai 则 必须 先学习课程 bi 。 例如,先修课程对 [0, 1] 表示:想要学习课程 0 ,你需要先

    2024年04月14日
    浏览(47)
  • LeetCode 0630.课程表 III:贪心 + 优先队列

    力扣题目链接:https://leetcode.cn/problems/course-schedule-iii/ 这里有 n 门不同的在线课程,按从 1 到 n  编号。给你一个数组 courses ,其中 courses[i] = [duration i , lastDay i ] 表示第 i 门课将会 持续 上 duration i 天课,并且必须在不晚于 lastDay i 的时候完成。 你的学期从第 1 天开始。且不能

    2024年02月09日
    浏览(37)
  • Python每日一练(20230505) 课程表 Course Schedule III/IV

    目录 3. 课程表 Course Schedule III 4. 课程表 Course Schedule IV 🌟 每日一练刷题专栏 🌟 Golang每日一练 专栏 Python每日一练 专栏 C/C++每日一练 专栏 Java每日一练 专栏 这里有  n  门不同的在线课程,按从  1  到  n  编号。给你一个数组  courses  ,其中  courses[i] = [durationi, lastDayi

    2024年02月03日
    浏览(36)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包