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

leetcode:210. 课程表 II

  1. 课程表 II
    提示
    中等
    889
    相关企业
    现在你总共有 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] 互不相同

方法一:深度优先搜索

class Solution {
private:// 存储有向图vector<vector<int>> edges;// 标记每个节点的状态:0=未搜索,1=搜索中,2=已完成vector<int> visited;// 用数组来模拟栈,下标 0 为栈底,n-1 为栈顶vector<int> result;// 判断有向图中是否有环bool valid = true;public:void dfs(int u) {// 将节点标记为「搜索中」visited[u] = 1;// 搜索其相邻节点// 只要发现有环,立刻停止搜索for (int v: edges[u]) {// 如果「未搜索」那么搜索相邻节点if (visited[v] == 0) {dfs(v);if (!valid) {return;}}// 如果「搜索中」说明找到了环else if (visited[v] == 1) {valid = false;return;}}// 将节点标记为「已完成」visited[u] = 2;// 将节点入栈result.push_back(u);}vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {edges.resize(numCourses);visited.resize(numCourses);for (const auto& info: prerequisites) {edges[info[1]].push_back(info[0]);}// 每次挑选一个「未搜索」的节点,开始进行深度优先搜索for (int i = 0; i < numCourses && valid; ++i) {if (!visited[i]) {dfs(i);}}if (!valid) {return {};}// 如果没有环,那么就有拓扑排序// 注意下标 0 为栈底,因此需要将数组反序输出reverse(result.begin(), result.end());return result;}
};

方法二:广度优先搜索

class Solution {
private:// 存储有向图vector<vector<int>> edges;// 存储每个节点的入度vector<int> indeg;// 存储答案vector<int> result;public:vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {edges.resize(numCourses);indeg.resize(numCourses);for (const auto& info: prerequisites) {edges[info[1]].push_back(info[0]);++indeg[info[0]];}queue<int> q;// 将所有入度为 0 的节点放入队列中for (int i = 0; i < numCourses; ++i) {if (indeg[i] == 0) {q.push(i);}}while (!q.empty()) {// 从队首取出一个节点int u = q.front();q.pop();// 放入答案中result.push_back(u);for (int v: edges[u]) {--indeg[v];// 如果相邻节点 v 的入度为 0,就可以选 v 对应的课程了if (indeg[v] == 0) {q.push(v);}}}if (result.size() != numCourses) {return {};}return result;}
};

相关文章:

leetcode:210. 课程表 II

课程表 II 提示 中等 889 相关企业 现在你总共有 numCourses 门课需要选&#xff0c;记为 0 到 numCourses - 1。给你一个数组 prerequisites &#xff0c;其中 prerequisites[i] [ai, bi] &#xff0c;表示在选修课程 ai 前 必须 先选修 bi 。 例如&#xff0c;想要学习课程…...

[MT8766][Android12] 使用谷歌LPA实现ESIM功能的流程

文章目录 开发平台基本信息问题描述实现流程 其他问题 开发平台基本信息 芯片: MT8766 版本: Android 12 kernel: msm-4.19 问题描述 客户需要我们设备支持ESIM功能&#xff0c;5月份的时候在高通6125上面预研过ESIM功能&#xff0c;当时ESIM供应商是Links field&#xff0c…...

MyBatis-Plus为简化开发而生

简介 MyBatis-Plus 简称 MP是一个 MyBatis 的增强工具&#xff0c;在 MyBatis 的基础上只做增强不做改变&#xff0c;为简化开发、提高效率而生。 他们的愿景是成为 MyBatis 最好的搭档&#xff0c;就像魂斗罗中的 1P、2P&#xff0c;基友搭配&#xff0c;效率翻倍。 特性 无…...

【翻译】Efficient Data Loader for Fast Sampling-Based GNN Training on Large Graphs

转载请注明出处&#xff1a;小锋学长生活大爆炸[xfxuezhang.cn] 此内容为机器翻译的结果&#xff0c;若有异议的地方&#xff0c;建议查看原文。 机器翻译的一些注意点&#xff0c;比如&#xff1a; 纪元、时代 > epoch工人 > worker火车、培训、训练师 > train Effic…...

OPUS解码器PLC

OPUS解码器支持PLC&#xff08;Packet Loss Concealment&#xff09;技术。 在音频通信中&#xff0c;网络丢包是常见的情况。当网络丢失一些音频数据包时&#xff0c;接收端可能无法正常解码并播放这些丢失的音频信号&#xff0c;导致声音中断或质量下降。为了改善这种情况&a…...

Rancher 使用指南

Rancher 使用指南 Rancher 是什么?Rancher 与 OpenShift / Kubesphere 主要区别对比RancherOpenShiftKubesphere 对比 Rancher 和 OpenShift Rancher 安装 Rancher 是什么? 企业级Kubernetes管理平台 Rancher 是供采用容器的团队使用的完整软件堆栈。它解决了管理多个Kuber…...

百度SEO优化全攻略(提高网站排名的5个方面)

百度SEO入门介绍&#xff1a; 随着互联网的不断发展&#xff0c;SEO已经成为网站优化的重要一环。而百度作为中国最大的搜索引擎&#xff0c;其SEO优化更是至关重要。SEO不仅能够提高网站排名&#xff0c;还能够提高网站流量、用户体验以及品牌知名度。因此&#xff0c;掌握百…...

华为云云耀云服务器L实例评测|华为云耀云服务器L实例私有库搭建verdaccio(八)

九、华为云耀云服务器L实例私有库搭建verdaccio&#xff1a; Verdaccio 是一个简单的、零配置本地私有 npm 软件包代理注册表。Verdaccio 开箱即用&#xff0c;拥有自己的小型数据库&#xff0c;能够代理其它注册表&#xff08;例如 npmjs.org&#xff09;&#xff0c;缓存下载…...

C语言之动态内存管理_柔性数组篇(2)

目录 柔性数组的特点 柔性数组的使用 动态内存函数增容柔性数组模拟实现 柔性数组的优势 今天接着来讲解一下柔性数组知识。 柔性数组的特点 C99中&#xff0c;结构中的最后一个元素允许是未知大小的数组&#xff0c;这就叫做【柔性数组】成员。 结构体中最后一个成员未…...

vue基础

引入vue文件 <div id"app"><!--{{}}插值表达式&#xff0c;绑定vue中的data数据-->{{message}} </div><script src"vue.min.js"></script> <script>new Vue({el:#app,data:{message:Hello Vue}}) </script>单项…...

访问量突破1W,纪念一下~

Mr.kanglong&#xff0c; 继续加油&#xff01;...

C# 处理TCP数据的类(服务端)

using System; using System.Collections.Generic; using System.Net; using System.Net.Sockets; using System.Threading;namespace TestDemo {/// <summary>/// 处理TCP数据的类&#xff08;服务端&#xff09;/// </summary>public class TcpService{/// <s…...

【Jenkins】调用API构建并钉钉通知

文章目录 Jenkins API介绍提交作业带参数的作业API 令牌 Shell调用代码 Jenkins API介绍 Jenkins 提供了远程访问 API。目前它有三种格式&#xff1a; XML JSON Python 远程访问 API 形式为"…/api/" 例如&#xff0c; Jenkins 安装位于https://ci.jenkins.io&a…...

Java NIO三大核心组件

文章目录 一、Buffer1、重要属性2、重要方法1&#xff09;allocate()创建缓冲区2&#xff09;put()写入到缓冲区3&#xff09;flip()翻转4&#xff09;get()从缓冲区读取5&#xff09;rewind()倒带6&#xff09;mark()和reset()7&#xff09;clear()清空缓冲区8&#xff09;使用…...

js数据排序方法(sort)?

在JavaScript中&#xff0c;可以使用Array的sort()方法对数据进行排序。下面是一个基本的例子&#xff0c;它展示了如何对一个数组进行升序和降序排序&#xff1a; // 创建一个数字数组 let numbers [2, 9, 1, 5, 8, 6];// 升序排序 let ascending numbers.sort(function(a,…...

若依框架学习笔记_mybatis

一、 在框架中引用的先后顺序 在ruoyi-system的resources下的xml中定义方法在java下的mapper包中引用方法在java下的service包中再引用mapper的方法 二、xml中的写法 标签&#xff1a; resultMap 返回数据sql 查询语句 可包含在其他操作中select 查询insert 插入update 更新…...

虚拟机的发展史:从分时系统到容器化

一、前世 早期计算机的价格非常昂贵&#xff0c;一台计算机可能需要花费几十万甚至上百万美元。例如&#xff0c;ENIAC计算机&#xff0c;作为世界上第一台通用电子数字计算机&#xff0c;当时的造价约为48万美元。科学家或者工程师们需要计算机的能力&#xff0c;但是买不起整…...

季涨约3~8%,DRAM合约价大幅回升 | 百能云芯

据TrendForce的研究显示&#xff0c;第4季DRAM与NAND Flash均价将开始全面上涨。特别是DRAM&#xff0c;预计第4季的合约价将季涨幅约在3%到8%之间。然而&#xff0c;这波上涨是否能持续&#xff0c;取决于供应商是否坚守减产策略以及实际需求的回升程度&#xff0c;尤其值得关…...

LocalDate的用法

日期时间转换 2023-03-30 14:25:00.000 DateTimeFormat(pattern "yyyy-MM-dd HH:mm:ss:sss")private LocalDateTime requestTimeStamp; 2021-06-18T10:46:19.67378508:00 new SimpleDateFormat("yyyy-MM-ddTHH:mm:ss:sssXXX");yyyy-mm-dd hh:mm:ss.sss 05…...

React通过ref获取子组件的数据和方法

父组件 1) ref必须传值, 否则childRef拿不到子组件的数据和方法 注意: 不一定使用app组件, 其他的任何父组件都可以 import "./App.css"; import React, { useEffect, useRef } from "react"; import RefToGetChild from "./components/RefToGetCh…...

生成xcframework

打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式&#xff0c;可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...

.Net框架,除了EF还有很多很多......

文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...

在四层代理中还原真实客户端ngx_stream_realip_module

一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡&#xff08;如 HAProxy、AWS NLB、阿里 SLB&#xff09;发起上游连接时&#xff0c;将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后&#xff0c;ngx_stream_realip_module 从中提取原始信息…...

WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)

一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解&#xff0c;适合用作学习或写简历项目背景说明。 &#x1f9e0; 一、概念简介&#xff1a;Solidity 合约开发 Solidity 是一种专门为 以太坊&#xff08;Ethereum&#xff09;平台编写智能合约的高级编…...

Android第十三次面试总结(四大 组件基础)

Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成&#xff0c;用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机&#xff1a; ​onCreate()​​ ​调用时机​&#xff1a;Activity 首次创建时调用。​…...

使用Matplotlib创建炫酷的3D散点图:数据可视化的新维度

文章目录 基础实现代码代码解析进阶技巧1. 自定义点的大小和颜色2. 添加图例和样式美化3. 真实数据应用示例实用技巧与注意事项完整示例(带样式)应用场景在数据科学和可视化领域,三维图形能为我们提供更丰富的数据洞察。本文将手把手教你如何使用Python的Matplotlib库创建引…...

Java毕业设计:WML信息查询与后端信息发布系统开发

JAVAWML信息查询与后端信息发布系统实现 一、系统概述 本系统基于Java和WML(无线标记语言)技术开发&#xff0c;实现了移动设备上的信息查询与后端信息发布功能。系统采用B/S架构&#xff0c;服务器端使用Java Servlet处理请求&#xff0c;数据库采用MySQL存储信息&#xff0…...

Qemu arm操作系统开发环境

使用qemu虚拟arm硬件比较合适。 步骤如下&#xff1a; 安装qemu apt install qemu-system安装aarch64-none-elf-gcc 需要手动下载&#xff0c;下载地址&#xff1a;https://developer.arm.com/-/media/Files/downloads/gnu/13.2.rel1/binrel/arm-gnu-toolchain-13.2.rel1-x…...

OD 算法题 B卷【正整数到Excel编号之间的转换】

文章目录 正整数到Excel编号之间的转换 正整数到Excel编号之间的转换 excel的列编号是这样的&#xff1a;a b c … z aa ab ac… az ba bb bc…yz za zb zc …zz aaa aab aac…; 分别代表以下的编号1 2 3 … 26 27 28 29… 52 53 54 55… 676 677 678 679 … 702 703 704 705;…...

第八部分:阶段项目 6:构建 React 前端应用

现在&#xff0c;是时候将你学到的 React 基础知识付诸实践&#xff0c;构建一个简单的前端应用来模拟与后端 API 的交互了。在这个阶段&#xff0c;你可以先使用模拟数据&#xff0c;或者如果你的后端 API&#xff08;阶段项目 5&#xff09;已经搭建好&#xff0c;可以直接连…...