当前位置: 首页 > news >正文

【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---拓扑排序

一、拓扑排序的定义&#xff1a; 先引用一段百度百科上对于拓扑排序的定义&#xff1a; 对一个有向无环图 ( Directed Acyclic Graph 简称 DAG ) G 进行拓扑排序&#xff0c;是将 G 中所有顶点排成一个线性序列&#xff0c;使得图中任意一对顶点 u 和 v &#xff0c;若边 <…...

STM32CubeMX systick bug?

发觉用新版&#xff08;V6.9.1&#xff09;的它生成代码&#xff0c;会有问题。可能是 BUG。具体如下&#xff1a; 一个简单的点灯程序&#xff0c;用 Keil MDK 5.38a&#xff08;compiler version 6&#xff09;编译。 如果在变量前&#xff0c;不加上关键字“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​,Xt​​Any π \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&#xff0c;但是不知道到在vs里面build时一直报错&#xff0c;后面换了4.7.0的版本测试&#xff0c;安装成功。 Release OpenCV 4.5.4 opencv/opencv GitHub 这个里面有官方预编译好的OpenCV库&#xff0c;可以直接食用。 扩展包&am…...

基于减法优化SABO优化ELM(SABO-ELM)负荷预测(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

记录第一个启动代码的诞生

核使用R52&#xff0c;参考汇编模板&#xff0c;一步一步来实现。 首先是ld文件&#xff0c;这个没啥好说的&#xff0c;主要是关注给vector_table划一块地址、stack地址&#xff0c;如下&#xff1a; .text.intvec :{_vectors_start .;KEEP(*(.text.intvec))_vectors_end .;…...

基于STM32的简化版智能手表

一、前言 本文的OLED多级菜单UI为一个综合性的STM32小项目&#xff0c;使用多传感器与OLED显示屏实现智能终端的效果。项目中的多级菜单UI使用了较为常见的结构体索引法去实现功能与功能之间的来回切换&#xff0c;搭配DHT11&#xff0c;RTC&#xff0c;LED&#xff0c;KEY等器…...

揭秘弹幕游戏制作

最近好多人问弹幕游戏&#xff0c;甚至是招人的也要DOTS做弹幕游戏... 实际上目前的弹幕游戏绝大多数应该和DOTS没有半点关系&#xff0c;别忘了DOTS这项技术渲染问题还没能够被合理解决呢 所以目前用的全都是GPU Instance这项技术&#xff0c;于是乎我决定下场写这篇帖子&am…...

2327. 知道秘密的人数;1722. 执行交换操作后的最小汉明距离;2537. 统计好子数组的数目

2327. 知道秘密的人数 核心思想&#xff1a;动态规划&#xff0c;每天的人可以分为三种&#xff0c;可分享秘密的人&#xff0c;不可分享秘密的人&#xff0c;忘记秘密的人。定义f[i]为第i天可分享秘密的人&#xff0c;那么第(idelay ,iforget)天&#xff0c;会增加f[i]个可分…...

【TCPDF】使用TCPDF导出PDF文件

目录 一、安装TCPDF类库 二、安装字体 三、使用TCPDF导出PDF文件 目的&#xff1a;PHP通过TCPDF类库导出文件为PDF。 开发语言及类库&#xff1a;ThinkPHP、TCPDF 效果图如下 一、安装TCPDF类库 在项目根目录使用composer安装TCPDF&#xff0c;安装完成后会在vendor目录下…...

MacBook苹果电脑重装、降级系统

1、下载balenaEtcher镜像启动盘制作工具 https://tails.net/etcher/balenaEtcher-portable.exe 2、选择从文件烧录选择下载好的Mac 镜像文件 百度网盘 请输入提取码&#xff08;Mac OS 10.10-12版本镜像文件&#xff09; 第二步选择目标磁盘&#xff0c;这里需要准备一块1…...

Java 解决long类型数据在前后端传递失真问题

问题&#xff1a;雪花算法的id长度为19位&#xff0c;前端能够接收的数字最多只能是16位的&#xff0c;因此就会造成精度丢失&#xff0c;得到的ID不是真正的ID。 解决&#xff1a; 在拦截器中加入Long类型转换&#xff0c;返回给前端string package io.global.iot.common.c…...

IDEA的快捷键大全

快捷键 说明 IntelliJ IDEA 的便捷操作性&#xff0c;快捷键的功劳占了一大半&#xff0c;对于各个快捷键组合请认真对待。IntelliJ IDEA 本身的设计思维是提倡键盘优先于鼠标的&#xff0c;所以各种快捷键组合层出不穷&#xff0c;对于快捷键设置也有各种支持&#xff0c;对…...

简单记一下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 的接口&#xff0c;使用该接口发布代码到 http://xxx-local/{name}/{project} &#xff0c;报了 Post "http://localhost:3000/api/internal/hook/pre-receive/{name}/{project} 相关的异常。具体内容如下&#xff1a; Gitea: In…...

如何使用element-ui相关组件如:el-select,el-table,el-switch,el-pagination,el-dialog

element-ui 官方链接&#xff1a; 组件 | Elementhttps://element.eleme.cn/#/zh-CN/component/installation el-select <!-- 用户类型选择框<template> 看情况使用value选择框绑定的值 命名必须是value不能改v-for"item in Options" options数据源来自于…...

微信小程序+echart实现点亮旅游地图

背景 最近看抖音有个很火的特效就是点亮地图&#xff0c;去过哪些地方&#xff0c;于是乎自己也想做一个&#xff0c;结合自己之前做的以家庭为单位的小程序&#xff0c;可以考虑做一个家庭一起点亮地图的功能。 效果图 过程 1&#xff0c;首先就是得去下微信小程序适配的ec…...

Git(8)——Git命令总结

一、简介 本篇文章将基于Git&#xff08;4&#xff09;——Git命令小总结&#xff0c;补充后续的Git使用命令 二、总结 # 添加远程连接 git remote add origin 远端地址# 推送本地代码 git push origin 分支名称# 拉取远端代码(第一次) git clone 远端克隆地址# 更新远端代码…...

9.15 滴滴笔试

T1&#xff08;二分&#xff09; #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 &…...

7.4.分块查找

一.分块查找的算法思想&#xff1a; 1.实例&#xff1a; 以上述图片的顺序表为例&#xff0c; 该顺序表的数据元素从整体来看是乱序的&#xff0c;但如果把这些数据元素分成一块一块的小区间&#xff0c; 第一个区间[0,1]索引上的数据元素都是小于等于10的&#xff0c; 第二…...

MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例

一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...

抖音增长新引擎:品融电商,一站式全案代运营领跑者

抖音增长新引擎&#xff1a;品融电商&#xff0c;一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中&#xff0c;品牌如何破浪前行&#xff1f;自建团队成本高、效果难控&#xff1b;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...

微服务商城-商品微服务

数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...

HTML前端开发:JavaScript 常用事件详解

作为前端开发的核心&#xff0c;JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例&#xff1a; 1. onclick - 点击事件 当元素被单击时触发&#xff08;左键点击&#xff09; button.onclick function() {alert("按钮被点击了&#xff01;&…...

【7色560页】职场可视化逻辑图高级数据分析PPT模版

7种色调职场工作汇报PPT&#xff0c;橙蓝、黑红、红蓝、蓝橙灰、浅蓝、浅绿、深蓝七种色调模版 【7色560页】职场可视化逻辑图高级数据分析PPT模版&#xff1a;职场可视化逻辑图分析PPT模版https://pan.quark.cn/s/78aeabbd92d1...

云原生安全实战:API网关Kong的鉴权与限流详解

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关&#xff08;API Gateway&#xff09; API网关是微服务架构中的核心组件&#xff0c;负责统一管理所有API的流量入口。它像一座…...

【C++特殊工具与技术】优化内存分配(一):C++中的内存分配

目录 一、C 内存的基本概念​ 1.1 内存的物理与逻辑结构​ 1.2 C 程序的内存区域划分​ 二、栈内存分配​ 2.1 栈内存的特点​ 2.2 栈内存分配示例​ 三、堆内存分配​ 3.1 new和delete操作符​ 4.2 内存泄漏与悬空指针问题​ 4.3 new和delete的重载​ 四、智能指针…...

LLMs 系列实操科普(1)

写在前面&#xff1a; 本期内容我们继续 Andrej Karpathy 的《How I use LLMs》讲座内容&#xff0c;原视频时长 ~130 分钟&#xff0c;以实操演示主流的一些 LLMs 的使用&#xff0c;由于涉及到实操&#xff0c;实际上并不适合以文字整理&#xff0c;但还是决定尽量整理一份笔…...

08. C#入门系列【类的基本概念】:开启编程世界的奇妙冒险

C#入门系列【类的基本概念】&#xff1a;开启编程世界的奇妙冒险 嘿&#xff0c;各位编程小白探险家&#xff01;欢迎来到 C# 的奇幻大陆&#xff01;今天咱们要深入探索这片大陆上至关重要的 “建筑”—— 类&#xff01;别害怕&#xff0c;跟着我&#xff0c;保准让你轻松搞…...