java实现课程表 II

这篇具有很好参考价值的文章主要介绍了java实现课程表 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]

思路:

利用列表和栈等数据结构,通过深度优先遍历就行排列优先级。具体代码如下。

代码:文章来源地址https://www.toymoban.com/news/detail-706664.html

class Solution {
    private List<Integer>[] list;
    private boolean isValid = true;
    private int[] visited;
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        visited = new int[numCourses];
        Stack<Integer> stack = new Stack<>();
        list = new ArrayList[numCourses];
        for(int i = 0; i <numCourses; i++){
            list[i] = new ArrayList<>();
        }
        for(int[] arr: prerequisites){
            list[arr[1]].add(arr[0]);
        }
        //讲数据加入栈中
        for(int i = 0; i < numCourses&&isValid;i++){
            if(visited[i] == 0) dfs(i,stack);
        }
        if(!isValid){
            return new int[]{};
        }
        int[] ans = new int[numCourses];
        int i = 0;
        while(!stack.isEmpty()){
            ans[i++] = stack.pop();
        }
        return ans;
    }
    private void dfs(Integer node,Stack<Integer> stack){
        visited[node] = -1;
        List<Integer> templist = list[node];
        for(Integer s: templist){
            //没有访问过的节点
            if(visited[s] == 0){
                dfs(s,stack);
                //存在环形,直接返回
            } else if(visited[s] == -1){
                isValid = false;
                return;
            }
        }
        //成功访问
        visited[node] = 1;
        stack.push(node);
    }
}

到了这里,关于java实现课程表 II的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 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日
    浏览(35)
  • 2023-09-10 LeetCode每日一题(课程表 II)

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

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

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

    2024年02月09日
    浏览(32)
  • vue实现动态课程表(TimeTable)

      (1)动态生成课程节数、时间周期        (2)遇到学科相等的可进行行合并、已解决合并后表格变形问题 (1)moment

    2024年02月04日
    浏览(39)
  • 【LeetCode热题100】打卡第38天:课程表&实现前缀树

    大家好,我是知识汲取者,欢迎来到我的LeetCode热题100刷题专栏! 精选 100 道力扣(LeetCode)上最热门的题目,适合初识算法与数据结构的新手和想要在短时间内高效提升的人,熟练掌握这 100 道题,你就已经具备了在代码世界通行的基本能力。在此专栏中,我们将会涵盖各种

    2024年02月17日
    浏览(52)
  • 自制课程表小程序

    微信开发者工具:稳定版 Stable Build 根据自己电脑的系统下载对应的版本 完整代码连接: https://pan.baidu.com/s/1VbgPOS6CUOae8vg2axhGIg?pwd=hk9e 提取码:hk9e 先把完整代码的压缩包解压,并记住这个路径,后面要用 1.打开下载好的微信开发工具, 注意不要用游客登录 ,我一开始就是游客

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

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

    2023年04月24日
    浏览(42)
  • 【图论】Leetcode 207. 课程表【中等】

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

    2024年04月14日
    浏览(45)
  • leetcode 630. 课程表 III

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

    2024年02月16日
    浏览(41)
  • 刷题笔记25——图论课程表

    为了最终理解你所不理解的,你必须经历一条愚昧无知的道路。为了占有你从未占有的东西,你必须经历被剥夺的道路。为了达到你现在所不在的名位,你必须经历那条你不在其中的道路。——艾略特 非常奇妙,我最初的错误是如下,在找到目标节点后直接加入到res中,但是

    2024年02月07日
    浏览(38)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包