剑指 Offer II 113. 课程顺序
comments: true
edit_url: https://github.com/doocs/leetcode/edit/main/lcof2/%E5%89%91%E6%8C%87%20Offer%20II%20113.%20%E8%AF%BE%E7%A8%8B%E9%A1%BA%E5%BA%8F/README.md
剑指 Offer II 113. 课程顺序
题目描述
现在总共有 numCourses
门课需要选,记为 0
到 numCourses-1
。
给定一个数组 prerequisites
,它的每一个元素 prerequisites[i]
表示两门课程之间的先修顺序。 例如 prerequisites[i] = [ai, bi]
表示想要学习课程 ai
,需要先完成课程 bi
。
请根据给出的总课程数 numCourses
和表示先修顺序的 prerequisites
得出一个可行的修课序列。
可能会有多个正确的顺序,只要任意返回一种就可以了。如果不可能完成所有课程,返回一个空数组。
示例 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,1,2,3] or [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 门课,直接修第一门课就可。
提示:
1 <= numCourses <= 2000
0 <= prerequisites.length <= numCourses * (numCourses - 1)
prerequisites[i].length == 2
0 <= ai, bi < numCourses
ai != bi
prerequisites
中不存在重复元素
注意:本题与主站 210 题相同:https://leetcode.cn/problems/course-schedule-ii/
解法
方法一:拓扑排序
拓扑排序的思路是,先统计每个节点的入度,然后从入度为 0 的节点开始,依次删除这些节点,同时更新与这些节点相连的节点的入度,直到所有节点都被删除。
这里使用队列来存储入度为 0 的节点,每次从队列中取出一个节点,将其加入结果数组中,然后遍历与这个节点相连的节点,将这些节点的入度减 1,如果减 1 后入度为 0,则将这些节点加入队列中。
最后判断结果数组的长度是否等于节点的个数,如果等于则返回结果数组,否则返回空数组。
时间复杂度 O ( n + m ) O(n + m) O(n+m),空间复杂度 O ( n + m ) O(n + m) O(n+m)。其中 n n n 和 m m m 分别是节点的个数和边的个数。
Python3
class Solution:def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:graph=defaultdict(list)indg={} #其实目的还是为bfs第一层服务的for i in range(numCourses): #【注意】初始化,要不然第一层为空indg[i]=0 for b,a in prerequisites:graph[a].append(b)indg[b]+=1# 第一层q=deque()for node,ind in indg.items():if ind==0:q.append(node)print(q,indg)#bfsres=[]while q:for _ in range(len(q)):cur=q.popleft()res.append(cur)for nx in graph[cur]:indg[nx]-=1if indg[nx]==0:q.append(nx)return res if len(res)==numCourses else []
Java
class Solution {public int[] findOrder(int numCourses, int[][] prerequisites) {List<Integer>[] g = new List[numCourses];Arrays.setAll(g, k -> new ArrayList<>());int[] indeg = new int[numCourses];for (var p : prerequisites) {int a = p[0], b = p[1];g[b].add(a);++indeg[a];}Deque<Integer> q = new ArrayDeque<>();for (int i = 0; i < numCourses; ++i) {if (indeg[i] == 0) {q.offer(i);}}int[] ans = new int[numCourses];int cnt = 0;while (!q.isEmpty()) {int i = q.poll();ans[cnt++] = i;for (int j : g[i]) {if (--indeg[j] == 0) {q.offer(j);}}}return cnt == numCourses ? ans : new int[0];}
}
C++
class Solution {
public:vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {vector<int> g[numCourses];vector<int> indeg(numCourses);for (auto& p : prerequisites) {int a = p[0], b = p[1];g[b].push_back(a);++indeg[a];}queue<int> q;for (int i = 0; i < numCourses; ++i) {if (indeg[i] == 0) {q.push(i);}}vector<int> ans;while (q.size()) {int i = q.front();q.pop();ans.push_back(i);for (int j : g[i]) {if (--indeg[j] == 0) {q.push(j);}}}return ans.size() == numCourses ? ans : vector<int>();}
};
Go
func findOrder(numCourses int, prerequisites [][]int) []int {g := make([][]int, numCourses)indeg := make([]int, numCourses)for _, p := range prerequisites {a, b := p[0], p[1]g[b] = append(g[b], a)indeg[a]++}q := []int{}for i, v := range indeg {if v == 0 {q = append(q, i)}}ans := []int{}for len(q) > 0 {i := q[0]q = q[1:]ans = append(ans, i)for _, j := range g[i] {indeg[j]--if indeg[j] == 0 {q = append(q, j)}}}if len(ans) == numCourses {return ans}return []int{}
}
TypeScript
function findOrder(numCourses: number, prerequisites: number[][]): number[] {const g: number[][] = Array.from({ length: numCourses }, () => []);const indeg: number[] = Array(numCourses).fill(0);for (const [a, b] of prerequisites) {g[b].push(a);++indeg[a];}const q: number[] = indeg.map((v, i) => (v === 0 ? i : -1)).filter(v => v !== -1);const ans: number[] = [];while (q.length) {const i = q.pop()!;ans.push(i);for (const j of g[i]) {if (--indeg[j] === 0) {q.push(j);}}}return ans.length === numCourses ? ans : [];
}
C#
public class Solution {public int[] FindOrder(int numCourses, int[][] prerequisites) {List<int>[] g = new List<int>[numCourses];for (int i = 0; i < numCourses; i++) {g[i] = new List<int>();}int[] indeg = new int[numCourses];foreach (var p in prerequisites) {int a = p[0], b = p[1];g[b].Add(a);++indeg[a];}Queue<int> q = new Queue<int>();for (int i = 0; i < numCourses; ++i) {if (indeg[i] == 0) {q.Enqueue(i);}}int[] ans = new int[numCourses];int cnt = 0;while (q.Count > 0) {int i = q.Dequeue();ans[cnt++] = i;foreach (int j in g[i]) {if (--indeg[j] == 0) {q.Enqueue(j);}}}return cnt == numCourses ? ans : new int[0];}
}
Swift
class Solution {func findOrder(_ numCourses: Int, _ prerequisites: [[Int]]) -> [Int] {var graph = Array(repeating: [Int](), count: numCourses)var indegree = Array(repeating: 0, count: numCourses)for prereq in prerequisites {let course = prereq[0]let prereqCourse = prereq[1]graph[prereqCourse].append(course)indegree[course] += 1}var queue = [Int]()for i in 0..<numCourses {if indegree[i] == 0 {queue.append(i)}}var order = [Int]()while !queue.isEmpty {let course = queue.removeFirst()order.append(course)for nextCourse in graph[course] {indegree[nextCourse] -= 1if indegree[nextCourse] == 0 {queue.append(nextCourse)}}}return order.count == numCourses ? order : []}
}
相关文章:
剑指 Offer II 113. 课程顺序
comments: true edit_url: https://github.com/doocs/leetcode/edit/main/lcof2/%E5%89%91%E6%8C%87%20Offer%20II%20113.%20%E8%AF%BE%E7%A8%8B%E9%A1%BA%E5%BA%8F/README.md 剑指 Offer II 113. 课程顺序 题目描述 现在总共有 numCourses 门课需要选,记为 0 到 n…...
蓝桥杯 小球反弹
问题描述 有一个长方形,长为 343720 单位长度,宽为 233333 单位长度。 在其内部左上角顶点有一小球(无视其体积),其初速度方向如图所示,且保持运动速率不变。分解到长宽两个方向上的速率之比为࿱…...
Python 监听模式(Observer Pattern)
1. 监听模式技术方案 监听模式(Observer Pattern)是一种行为设计模式,允许对象(称为“观察者”或“监听者”)在另一个对象(称为“被观察者”或“主题”)的状态发生变化时接收通知。这种模式的核…...
蓝桥备赛(25)算法篇【差分】
一、差分 前缀和和差分的核心思想是预处理 , 可以在暴力枚举的过程中 , 快速给出查询结果 , 从而优化时间复杂度 。 最经典的用空间替换时间的做法。 学完差分之后 , 大家会发现 , 前缀和与差分是一对互逆的运算 二、一…...
Linux|fork命令及其使用的写时拷贝技术
fork复制进程 fork通过以下步骤来复制进程: 分配新的进程控制块:内核为新进程分配一个新的进程控制块(PCB),用于存储进程的相关信息,如进程 ID、状态、寄存器值、内存指针等。复制进程地址空间࿱…...
sgpt 终端使用指南
1. 什么是 sgpt? sgpt 是一个基于 OpenAI API 的命令行工具,允许用户在终端中与 AI 进行交互,支持自然语言对话、代码生成、Shell 命令生成等功能。本文将介绍 sgpt 的安装方法、基本用法、配置文件路径及修改方式,并提供完整的配…...
python如何提取html中所有的图片链接
在Python中,你可以使用BeautifulSoup库来解析HTML内容,并提取其中所有的图片链接(即<img>标签的src属性)。以下是一个示例代码,展示了如何做到这一点: 首先,确保你已经安装了BeautifulSo…...
第十一章 | 智能合约主网部署与验证详解
📚 第十一章 | 智能合约主网部署与验证详解 ——让你的合约真正上线、公开、透明! ✅ 本章导读 前面我们写了各种合约,ERC20、NFT、DAO…… 但只在本地测试或测试网上部署运行,项目还没“上链”! 主网上线部署&#…...
一文读懂Python之json模块(33)
一、json模块介绍 json模块的功能是将序列化的json数据从文件里读取出来或者存入文件。json是一种轻量级的数据交换格式,在大部分语言中,它被理解为数组(array)。 json模块序列化与反序列化的过程分别是 encoding和 decoding。e…...
TextView、AppCompatTextView和MaterialTextView该用哪一个?Android UI 组件发展史与演进对照表
在 Android 开发中,UI 组件一直在不断演进,从最初的原生组件,到 Support Library(AppCompat 兼容库),再到如今的 Material Design 组件。这篇文章将梳理 Android UI 组件的发展历史,并提供详细的…...
三层网络 (服务器1 和 服务器2 在不同网段)
服务器1 和 服务器2 在不同网段,并且通过三层交换机实现通信 1. 网络拓扑 假设网络拓扑如下: 服务器1: mac0:IP 地址 192.168.1.10/24,网关 192.168.1.1 mac1:IP 地址 10.0.1.10/24,网关 10.0…...
23种设计模式-创建型模式-工厂方法
文章目录 简介场景问题1. 直接依赖具体实现2. 违反开闭原则3. 条件分支泛滥4. 代码重复风险 解决根本问题完整类图完整代码说明核心优势代码优化静态配置表动态策略 总结 简介 工厂方法是一种创建型设计模式,它提供了在父类中创建对象的接口,但允许子类…...
el-table单元格编辑,动态增删行,回车/上下左右箭头切换单元格
🤵 作者:coderYYY 🧑 个人简介:前端程序媛,目前主攻web前端,后端辅助,其他技术知识也会偶尔分享🍀欢迎和我一起交流!🚀(评论和私信一般会回!!) 👉 个人专栏推荐:《前端项目教程以及代码》 基于 Element UI 实现表格单元格编辑与键盘导航功能 Element UI …...
基于springboot的新闻推荐系统(045)
摘要 随着信息互联网购物的飞速发展,国内放开了自媒体的政策,一般企业都开始开发属于自己内容分发平台的网站。本文介绍了新闻推荐系统的开发全过程。通过分析企业对于新闻推荐系统的需求,创建了一个计算机管理新闻推荐系统的方案。文章介绍了…...
解决Selenium滑动页面到指定元素,点击失效的问题
White graces:个人主页 🙉专栏推荐:Java入门知识🙉 🐹今日诗词:君失臣兮龙为鱼,权归臣兮鼠变虎🐹 ⛳️点赞 ☀️收藏⭐️关注💬卑微小博主🙏 ⛳️点赞 ☀️收藏⭐️关注Ǵ…...
医学图像白血病分割数据集labelme格式245张5类别
数据集格式:labelme格式(不包含mask文件,仅仅包含jpg图片和对应的json文件) 图片数量(jpg文件个数):245 标注数量(json文件个数):245 标注类别数:5 标注类别名称:["basophil Leukemia","Lymphocyte…...
深度学习Python编程:从入门到工程实践
第一章 Python语言概述与生态体系 1.3 Python在工业界的应用场景 # 示例:使用FastAPI构建RESTful接口 from fastapi import FastAPI from pydantic import BaseModelapp = FastAPI()class Item(BaseModel):name: strprice: float@app.post("/items/") async def cr…...
DHCPv6 Stateless Vs Stateful Vs Stateless Stateful
DHCPv6常见配置模式 在 IPv6 网络中,DHCPv6 的 Stateless(无状态)、Stateful(有状态) 和 Stateless + Stateful(混合模式) 是三种常见的配置模式。它们的主要区别在于客户端如何获取 IPv6 地址和其他网络配置信息(如 DNS 服务器)。 Stateless(无状态)模式 Statele…...
Redis Cluster 详解
Redis Cluster 详解 1. 为什么需要 Redis Cluster? Redis 作为一个高性能的内存数据库,在单机模式下可能会遇到以下问题: 单机容量受限:Redis 是基于内存存储的,单机的内存资源有限,单实例的 Redis 只能…...
Spring(8)——MyBatis入门(2)
一、Mybatis的xml配置文件 Mybatis的开发有两种方式: 注解xml 上一篇博客介绍了用注解的方式操作数据库,这一篇介绍通过xml配置文件的方式操作数据库。 1.1 xml配置文件规则 在Mybatis中使用XML映射文件方式开发,需要符合一定的规范&…...
解析DeepSeek的技术内核:混合专家架构如何重塑AI效能
解析DeepSeek的技术内核:混合专家架构如何重塑AI效能 在当今大型语言模型(LLM)竞争激烈的赛道上,中国AI企业DeepSeek凭借其独特的技术路线脱颖而出。其核心优势之一,便是对混合专家(Mixture of Experts&…...
Android在kts中简单使用AIDL
Android在kts中简单使用AIDL AIDL相信做Android都有所了解,跨进程通信会经常使用,这里就不展开讲解原理跨进程通信的方式了,最近项目换成kts的方式,于是把aidl也换成了统一的方式,其中遇到了很多问题,这里…...
【C++】类和对象(匿名对象)
匿名对象 用 类型(实参) 定义出来的对象叫做匿名对象,相比之前我们定义的 类型 对象名(实参) 定义出来叫有名对象匿名对象生命周期只在当前一行,一般临时定义一个对象当前用一下即可,就可以定义匿名对象。 class A { public:A(int a 0):_a…...
Spring boot 3.4 后 SDK 升级,暨 UI API/MCP 计划
PS 写这篇文章后看到 A Deep Dive Into MCP and the Future of AI Tooling | Andreessen HorowitzWe explore what MCP is, how it changes the way AI interacts with tools, what developers are already building, and the challenges that still need solving. https://a1…...
使用Helm安装、 升级、 回滚Kubernetes应用
前言 在我之前做的项目里,我们对Microk8s微服务的更新是通过自制tar包的方式做的, tar包存储了镜像和YAML文件。 每次升级时,我们需要先删除所有的YAML资源,然后重新创建新的资源。 这种方式存在以下问题: 服务中断:…...
Text-to-SQL将自然语言转换为数据库查询语句
有关Text-To-SQL方法,可以查阅我的另一篇文章,Text-to-SQL方法研究 直接与数据库对话-text2sql Text2sql就是把文本转换为sql语言,这段时间公司有这方面的需求,调研了一下市面上text2sql的方法,比如阿里的Chat2DB,麻…...
gin学习
gin学习笔记,不仅包含了基本的增删查改外,还包括参数传递,上传下载,模版、session与中间件等,方便收藏自习可用 文章目录 获得个请求get打印字符串get请求xmlget请求跳转http方法路由可以通过Context的Param方法来获取…...
【HarmonyOS NEXT】关键资产存储开发案例
在 iOS 开发中 Keychain 是一个非常安全的存储系统,用于保存敏感信息,如密码、证书、密钥等。与文件系统不同,Keychain 提供了更高的安全性,因为它对数据进行了加密,并且只有经过授权的应用程序才能访问存储的数据。那…...
高德终端技术总结:高可用架构如何练成?
前言 高德地图作为国民级应用,特别是出行场景的独特性,要确保在线导航高并发和交通安全级的超稳定性,这对技术团队提出异乎寻常的高要求,无论是终端、云端,还是“终端-云端”之间的连接,都必须实现“高可用…...
STM32八股【3】------RAM和片上FLASH
1、RAM和FLASH构成 1.RAM ┌──────────────────────────┐ │ 栈区 (Stack) │ ← 从RAM顶端向下扩展(存储局部变量、函数调用信息) │--------------------------│ │ 堆区 (Heap) │ ← …...
Apache Doris
Apache Doris介绍 Apache Doris 是一个基于 MPP 架构的高性能、实时的分析型数据库,以极速易用的特点被人们所熟知,仅需亚秒级响应时间即可返回海量数据下的查询结果,不仅可以支持高并发的点查询场景,也能支持高吞吐的复杂分析场…...
Debezium介绍
1.什么是Debezium Debezium 是一个开源的分布式平台,用于捕获数据库的变更事件(CDC,Change Data Capture)。它能够实时捕获数据库中的行级更改,并将这些更改作为事件流发送到消息中间件(如 Apache Kafka&a…...
奇迹科技:蓝牙网关赋能少儿篮球教育的创新融合案例研究
一、引言 本文研究了福建奇迹运动体育科技有限公司(简称‘奇迹科技’)如何利用其创新产品体系和桂花网蓝牙网关M1500,与少儿篮球教育实现深度融合。重点分析其在提升教学效果、保障训练安全、优化个性化教学等方面的实践与成效,为…...
Python散点图(Scatter Plot):高阶分析、散点图矩阵、三维散点图及综合应用
散点图:数据分析的利器 在数据分析领域,散点图是一种直观且强大的可视化工具,广泛应用于揭示变量间的相关性以及识别数据集中的异常值。本文将深入探讨散点图的这两种关键功能,并结合实际案例与Python代码示例,带您全面了解散点图的应用。 一、散点图如何展示变量间的相…...
计算机网络层超全解析:从IP协议到路由算法
🌐 (专业详解生活化类比,逻辑一镜到底) 📖 网络层的核心使命 核心任务:在不同网络间为数据包选择最佳路径,实现端到端通信。 类比:快递公司总部(网络层)根据…...
RoboVQA
RoboVQA:面向机器人技术的多模态长时推理 摘要 我们提出了一种可扩展、自下而上且具有内在多样性的数据收集方案,适用于中长时高级推理任务,其吞吐量比传统的自上而下分步收集方法高2.2倍。通过在3栋办公楼内使用多种实体(机器人、人类、使用抓取工具的人类)执行任意用…...
javascript语法入门
一、变量声明 在JavaScript中,可以使用var、let和const来声明变量。 javascript var name "张三"; let age 20; 二、数据类型 JavaScript中有7种基本数据类型:undefined、null、boolean、string、symbol、number,以及object。…...
前端字段名和后端不一致?解锁 JSON 映射的“隐藏规则” !!!
🚀 前端字段名和后端不一致?解锁 JSON 映射的“隐藏规则” 🌟 嘿,技术冒险家们!👋 今天我们要聊一个开发中常见的“坑”:前端传来的 JSON 参数字段名和后端对象字段名不一致,会发生…...
Java——ArrayList集合
ArrayList:基于动态数组实现,支持随机访问,适合频繁的随机访问操作,但在插入和删除元素时性能较差。 技术层面介绍 所属类库:ArrayList 位于 java.util 包中,它实现了 List 接口,因此具备 Lis…...
基于python+django的图书借阅网站-图书借阅管理系统源码+运行步骤
该系统是基于pythondjango开发的在线图书借阅管理系统。系统适合场景:大学生、课程作业、系统设计、毕业设计。 演示地址 前台地址: http://book.gitapp.cn 后台地址:http://book.gitapp.cn/#/admin 后台管理帐号: 用户名&…...
Flutter运行错误:UG! exception in phase ‘semantic analysis‘
最近在Mac Mini M4上通过Android Studio导入Flutter项目并运行,结果一直跑不起来,错误日志如下: 执行命令查看版本信息: flutter doctor --verbose通过输出信息Java version OpenJDK Runtime Environment (build 21.0.41242208…...
Python-docx库详解:轻松实现Word文档自动化生成与图片尺寸控制
Python-docx库详解:轻松实现Word文档自动化生成与图片尺寸控制 在现代办公自动化的浪潮中,文档处理是一项不可或缺的任务。Python作为一种强大的编程语言,提供了丰富的库来简化这些任务。其中,python-docx库是处理Word文档的有力…...
【NLP 42、实践 ⑪ 用Bert模型结构实现自回归语言模型的训练】
目录 数据文件 一、模型定义 1.模型初始化 代码运行流程 2.前向传播,计算损失 ⭐ 代码运行流程 二、加载语料 代码运行流程 三、 随机生成样本 代码运行流程 四、建立模型 五、采样策略选择 代码运行流程 六、模型效果测试 代码运行流程 七、模型训练 代码运行流程 …...
HTTPS
目录 一 HTTPS是什么 二 加密 三 加密方案 四 CA机构/证书 五 最终方案(对称密钥/非对称密钥/CA证书)和总体流程 一 HTTPS是什么 在应用层存在SSL,TLS(HTTP之下,传输层之上)加密/解密安全协议,如果HTTP经过这个协议,对端也走…...
electron框架(4.0)electron-builde和electron Forge的打包方式
----使用electron-builder打包(需要魔法) --安装electron-builder: npm install electron-builder -D--package.json中进行相关配置: {"name": "video-tools","version": "1.0.0","main&quo…...
SaaS系统的销售微服务与权限微服务边界设计
在设计SaaS系统的销售微服务与权限微服务的边界时,需要结合领域驱动设计(DDD)和微服务拆分原则,确保高内聚、低耦合。以下是结合微服务架构原则、多租户SaaS需求及权限管理场景的完整设计方案,整合了权限服务与销售服务…...
Unity-AI-Deepseek生成的生成模型代码
结果 能用,不是很理想,从左到右,分别是body,眼睛,演睫毛,手指套(如果你知道这是什么)结果不是很理想 (下面代码已包含,修复的切线只能传Vector3参数,Unity2022测试) 你们帮我看看…...
Django REST Framework 请求封装源码解析与实现流程
版本说明: Django: V4.2.20 Django Rest Framework: V3.15.2 一、核心封装流程示意图 #mermaid-svg-qXJLIa9Bx1TCiPSN {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-qXJLIa9Bx1TCiPSN .error-icon{fill…...
简介PyCDE:Python CIRCT Design Entry
简介PyCDE:Python CIRCT Design Entry 引言 在硬件设计和验证领域,随着设计复杂性的增加,传统的方法往往难以满足现代设计的需求。PyCDE(Python CIRCT Design Entry)作为CIRCT项目的一部分,旨在为硬件设计…...
Python实现deepseek接口的调用
简介:DeepSeek 是一个强大的大语言模型,提供 API 接口供开发者调用。在 Python 中,可以使用 requests 或 httpx 库向 DeepSeek API 发送请求,实现文本生成、代码补全,知识问答等功能。本文将介绍如何在 Python 中调用 …...