当前位置: 首页 > 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 &…...

Zustand 状态管理库:极简而强大的解决方案

Zustand 是一个轻量级、快速和可扩展的状态管理库&#xff0c;特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...

iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版​分享

平时用 iPhone 的时候&#xff0c;难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵&#xff0c;或者买了二手 iPhone 却被原来的 iCloud 账号锁住&#xff0c;这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...

为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?

在建筑行业&#xff0c;项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升&#xff0c;传统的管理模式已经难以满足现代工程的需求。过去&#xff0c;许多企业依赖手工记录、口头沟通和分散的信息管理&#xff0c;导致效率低下、成本失控、风险频发。例如&#…...

将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?

Otsu 是一种自动阈值化方法&#xff0c;用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理&#xff0c;能够自动确定一个阈值&#xff0c;将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

高等数学(下)题型笔记(八)空间解析几何与向量代数

目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...

深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南

&#x1f680; C extern 关键字深度解析&#xff1a;跨文件编程的终极指南 &#x1f4c5; 更新时间&#xff1a;2025年6月5日 &#x1f3f7;️ 标签&#xff1a;C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言&#x1f525;一、extern 是什么&#xff1f;&…...

初学 pytest 记录

安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...

Go 语言并发编程基础:无缓冲与有缓冲通道

在上一章节中&#xff0c;我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道&#xff0c;它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好&#xff0…...

【C++】纯虚函数类外可以写实现吗?

1. 答案 先说答案&#xff0c;可以。 2.代码测试 .h头文件 #include <iostream> #include <string>// 抽象基类 class AbstractBase { public:AbstractBase() default;virtual ~AbstractBase() default; // 默认析构函数public:virtual int PureVirtualFunct…...

02.运算符

目录 什么是运算符 算术运算符 1.基本四则运算符 2.增量运算符 3.自增/自减运算符 关系运算符 逻辑运算符 &&&#xff1a;逻辑与 ||&#xff1a;逻辑或 &#xff01;&#xff1a;逻辑非 短路求值 位运算符 按位与&&#xff1a; 按位或 | 按位取反~ …...