【Java|golang】210. 课程表 II---拓扑排序
一、拓扑排序的定义:
先引用一段百度百科上对于拓扑排序的定义:
对一个有向无环图 ( Directed Acyclic Graph 简称 DAG ) G 进行拓扑排序,是将 G
中所有顶点排成一个线性序列,使得图中任意一对顶点 u 和 v ,若边 < u , v > ∈ E ( G ),则 u 在线性序列中出现在 v之前。通常,这样的线性序列称为满足拓扑次序 ( Topological Order )
的序列,简称拓扑序列。简单的说,由某个集合上的一个偏序得到该集合上的一个全序,这个操作称之为拓扑排序。
总结起来有三个要点:
1.有向无环图;
2.序列里的每一个点只能出现一次;
3.任何一对 u 和 v ,u 总在 v 之前(这里的两个字母分别表示的是一条线段的两个端点,u 表示起点,v 表示终点);
二、样例:
现在你总共有 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] 互不相同
public int[] findOrder(int numCourses, int[][] prerequisites) {int[] inDegree=new int[numCourses];Map<Integer, List<Integer>> directMap = new HashMap<>();for (int[] prerequisite : prerequisites) {List<Integer> list = directMap.getOrDefault(prerequisite[1], new ArrayList<>());list.add(prerequisite[0]);directMap.put(prerequisite[1],list);inDegree[prerequisite[0]]++;}Queue<Integer> queue=new LinkedList<>();for (int i = 0; i < numCourses; i++) {if (inDegree[i] == 0) {queue.add(i);}}int index=0;int[] res = new int[numCourses];while (!queue.isEmpty()){Integer poll = queue.poll();res[index++]=poll;List<Integer> list = directMap.getOrDefault(poll, new ArrayList<>());for (Integer i : list) {inDegree[i]--;if (inDegree[i]==0){queue.add(i);}}}return index==numCourses?res:new int[0];}

func findOrder(numCourses int, prerequisites [][]int) []int {inDegree:=make([]int,numCourses)directMap:=make(map[int][]int,0)for _, v := range prerequisites {directMap[v[1]] = append(directMap[v[1]], v[0])inDegree[v[0]]++}queue:=make([]int,0)for i := 0; i < numCourses; i++ {if inDegree[i] == 0 {queue=append(queue, i)}}index:=0res := make([]int,numCourses)for len(queue)!=0 {poll := queue[0]queue=queue[1:]res[index]=pollindex++for _,i := range directMap[poll] {inDegree[i]--if inDegree[i]==0{queue=append(queue, i)}}}if index!=numCourses{return []int{}}return res
}

相关文章:
【Java|golang】210. 课程表 II---拓扑排序
一、拓扑排序的定义: 先引用一段百度百科上对于拓扑排序的定义: 对一个有向无环图 ( Directed Acyclic Graph 简称 DAG ) G 进行拓扑排序,是将 G 中所有顶点排成一个线性序列,使得图中任意一对顶点 u 和 v ,若边 <…...
STM32CubeMX systick bug?
发觉用新版(V6.9.1)的它生成代码,会有问题。可能是 BUG。具体如下: 一个简单的点灯程序,用 Keil MDK 5.38a(compiler version 6)编译。 如果在变量前,不加上关键字“volatile”&am…...
徐亦达机器学习:Kalman Filter 卡尔曼滤波笔记 (一)
P ( x t P(x_t P(xt| x t − 1 ) x_{t-1}) xt−1) P ( y t P(y_t P(yt| x t ) x_t) xt) P ( x 1 ) P(x_1) P(x1)Discrete State DM A X t − 1 , X t A_{X_{t-1},X_t} AXt−1,XtAny π \pi πLinear Gassian Kalman DM N ( A X t − 1 B , Q ) N(AX_{t-1}B,Q)…...
Java和vue的包含数组组件contains、includes
List<String> tempList Arrays.asList("10018","1007","10017","1012"); if(tempList.contains(initMap.get("asset_type_id").toString())){// todo 计算运营终点桩号-起点桩号BigDecimal diffSum collectNum(col…...
OpenCV_CUDA_VS编译安装
一、OpenCV 我这里是下载的OpenCV4.5.4,但是不知道到在vs里面build时一直报错,后面换了4.7.0的版本测试,安装成功。 Release OpenCV 4.5.4 opencv/opencv GitHub 这个里面有官方预编译好的OpenCV库,可以直接食用。 扩展包&am…...
基于减法优化SABO优化ELM(SABO-ELM)负荷预测(Matlab代码实现)
💥💥💞💞欢迎来到本博客❤️❤️💥💥 🏆博主优势:🌞🌞🌞博客内容尽量做到思维缜密,逻辑清晰,为了方便读者。 ⛳️座右铭&a…...
记录第一个启动代码的诞生
核使用R52,参考汇编模板,一步一步来实现。 首先是ld文件,这个没啥好说的,主要是关注给vector_table划一块地址、stack地址,如下: .text.intvec :{_vectors_start .;KEEP(*(.text.intvec))_vectors_end .;…...
基于STM32的简化版智能手表
一、前言 本文的OLED多级菜单UI为一个综合性的STM32小项目,使用多传感器与OLED显示屏实现智能终端的效果。项目中的多级菜单UI使用了较为常见的结构体索引法去实现功能与功能之间的来回切换,搭配DHT11,RTC,LED,KEY等器…...
揭秘弹幕游戏制作
最近好多人问弹幕游戏,甚至是招人的也要DOTS做弹幕游戏... 实际上目前的弹幕游戏绝大多数应该和DOTS没有半点关系,别忘了DOTS这项技术渲染问题还没能够被合理解决呢 所以目前用的全都是GPU Instance这项技术,于是乎我决定下场写这篇帖子&am…...
2327. 知道秘密的人数;1722. 执行交换操作后的最小汉明距离;2537. 统计好子数组的数目
2327. 知道秘密的人数 核心思想:动态规划,每天的人可以分为三种,可分享秘密的人,不可分享秘密的人,忘记秘密的人。定义f[i]为第i天可分享秘密的人,那么第(idelay ,iforget)天,会增加f[i]个可分…...
【TCPDF】使用TCPDF导出PDF文件
目录 一、安装TCPDF类库 二、安装字体 三、使用TCPDF导出PDF文件 目的:PHP通过TCPDF类库导出文件为PDF。 开发语言及类库:ThinkPHP、TCPDF 效果图如下 一、安装TCPDF类库 在项目根目录使用composer安装TCPDF,安装完成后会在vendor目录下…...
MacBook苹果电脑重装、降级系统
1、下载balenaEtcher镜像启动盘制作工具 https://tails.net/etcher/balenaEtcher-portable.exe 2、选择从文件烧录选择下载好的Mac 镜像文件 百度网盘 请输入提取码(Mac OS 10.10-12版本镜像文件) 第二步选择目标磁盘,这里需要准备一块1…...
Java 解决long类型数据在前后端传递失真问题
问题:雪花算法的id长度为19位,前端能够接收的数字最多只能是16位的,因此就会造成精度丢失,得到的ID不是真正的ID。 解决: 在拦截器中加入Long类型转换,返回给前端string package io.global.iot.common.c…...
IDEA的快捷键大全
快捷键 说明 IntelliJ IDEA 的便捷操作性,快捷键的功劳占了一大半,对于各个快捷键组合请认真对待。IntelliJ IDEA 本身的设计思维是提倡键盘优先于鼠标的,所以各种快捷键组合层出不穷,对于快捷键设置也有各种支持,对…...
简单记一下Vue router 路由中使用 vue-i18n 进行标题国际化
引入状态管理和国际化文件 import store from ../store import i18n from /configs/i18n使用状态管理设置路由当前国际化选项 // 使用状态管理 i18n.locale store.state.setStore.i18n??zh路由中使用i18n { path: /login, name: login, component: LoginPage, meta: { ti…...
【Gitea】 Post “http://localhost:3000/api/internal/hook/pre-receive/aa/bbb“ 异常
引 使用 JGit 做了一个发布代码到 Gitea 的接口,使用该接口发布代码到 http://xxx-local/{name}/{project} ,报了 Post "http://localhost:3000/api/internal/hook/pre-receive/{name}/{project} 相关的异常。具体内容如下: Gitea: In…...
如何使用element-ui相关组件如:el-select,el-table,el-switch,el-pagination,el-dialog
element-ui 官方链接: 组件 | Elementhttps://element.eleme.cn/#/zh-CN/component/installation el-select <!-- 用户类型选择框<template> 看情况使用value选择框绑定的值 命名必须是value不能改v-for"item in Options" options数据源来自于…...
微信小程序+echart实现点亮旅游地图
背景 最近看抖音有个很火的特效就是点亮地图,去过哪些地方,于是乎自己也想做一个,结合自己之前做的以家庭为单位的小程序,可以考虑做一个家庭一起点亮地图的功能。 效果图 过程 1,首先就是得去下微信小程序适配的ec…...
Git(8)——Git命令总结
一、简介 本篇文章将基于Git(4)——Git命令小总结,补充后续的Git使用命令 二、总结 # 添加远程连接 git remote add origin 远端地址# 推送本地代码 git push origin 分支名称# 拉取远端代码(第一次) git clone 远端克隆地址# 更新远端代码…...
9.15 滴滴笔试
T1(二分) #include <bits/stdc.h>#define endl \nusing namespace std;typedef long long LL;const int N 1e5 10;int n, k; int a[N];bool check(int mid) {int rec 1e9, cnt 1;for(int i 0; i < n; i ) {int j i;while(j < n &…...
【Axure高保真原型】引导弹窗
今天和大家中分享引导弹窗的原型模板,载入页面后,会显示引导弹窗,适用于引导用户使用页面,点击完成后,会显示下一个引导弹窗,直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...
零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?
一、核心优势:专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发,是一款收费低廉但功能全面的Windows NAS工具,主打“无学习成本部署” 。与其他NAS软件相比,其优势在于: 无需硬件改造:将任意W…...
springboot 百货中心供应链管理系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,百货中心供应链管理系统被用户普遍使用,为方…...
三维GIS开发cesium智慧地铁教程(5)Cesium相机控制
一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点: 路径验证:确保相对路径.…...
Debian系统简介
目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版ÿ…...
汇编常见指令
汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX(不访问内存)XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...
全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比
目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec? IPsec VPN 5.1 IPsec传输模式(Transport Mode) 5.2 IPsec隧道模式(Tunne…...
Linux离线(zip方式)安装docker
目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1:修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本:CentOS 7 64位 内核版本:3.10.0 相关命令: uname -rcat /etc/os-rele…...
GitFlow 工作模式(详解)
今天再学项目的过程中遇到使用gitflow模式管理代码,因此进行学习并且发布关于gitflow的一些思考 Git与GitFlow模式 我们在写代码的时候通常会进行网上保存,无论是github还是gittee,都是一种基于git去保存代码的形式,这样保存代码…...
适应性Java用于现代 API:REST、GraphQL 和事件驱动
在快速发展的软件开发领域,REST、GraphQL 和事件驱动架构等新的 API 标准对于构建可扩展、高效的系统至关重要。Java 在现代 API 方面以其在企业应用中的稳定性而闻名,不断适应这些现代范式的需求。随着不断发展的生态系统,Java 在现代 API 方…...
