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

【1462. 课程表 IV】

来源:力扣(LeetCode)

描述:

你总共需要上 numCourses 门课,课程编号依次为 0numCourses-1 。你会得到一个数组 prerequisite ,其中 prerequisites[i] = [ai, bi] 表示如果你想选 bi 课程,你 必须 先选 ai 课程。

  • 有的课会有直接的先修课程,比如如果想上课程 1 ,你必须先上课程 0 ,那么会以 [0,1] 数对的形式给出先修课程数对。

先决条件也可以是 间接 的。如果课程 a 是课程 b 的先决条件,课程 b 是课程 c 的先决条件,那么课程 a 就是课程 c 的先决条件。

你也得到一个数组 queries ,其中 queries[j] = [uj, vj]。对于第 j 个查询,您应该回答课程 uj 是否是课程 vj 的先决条件。

返回一个布尔数组 answer ,其中 answer[j] 是第 j 个查询的答案。

示例 1:

1

输入:numCourses = 2, prerequisites = [[1,0]], queries = [[0,1],[1,0]]
输出:[false,true]
解释:课程 0 不是课程 1 的先修课程,但课程 1 是课程 0 的先修课程。

示例 2:

输入:numCourses = 2, prerequisites = [], queries = [[1,0],[0,1]]
输出:[false,false]
解释:没有先修课程对,所以每门课程之间是独立的。

示例 3:

3

输入:numCourses = 3, prerequisites = [[1,2],[1,0],[2,0]], queries = [[1,0],[1,2]]
输出:[true,true]

提示:

  • 2 <= numCourses <= 100
  • 0 <= prerequisites.length <= (numCourses * (numCourses - 1) / 2)
  • prerequisites[i].length == 2
  • 0 <= ai, bi <= n - 1
  • ai != bi
  • 每一对 [ai, bi] 都 不同
  • 先修课程图中没有环。
  • 1 <= queries.length <= 104
  • 0 <= ui, vi <= n - 1
  • ui != vi

方法一:广度优先搜索 + 拓扑排序

思路与算法

题目给出 numCourses 门课(编号从 0 开始),并给出了一个长度为 n 的课程之间的制约关系数组 prerequisite ,其中 prerequisite[i] = [ai, bi] 表示在学习课程 bi 之前必须要完成课程 ai 的学习,即课程 ai 为 bi 的先决条件。我们可以将上述条件构建一张有向图——将每一个课程看作一个点(课程编号即为点的编号),每一个制约关系 prerequisite[i] = [ai,bi] 对应一条从点 ai 指向 bi 的有向边,并且题目保证了这样构建出来的图不存在环。

现在有 m 个查询 queries,其中对于第 i 个查询 queries[i] = [ui,vi],我们需要判断课程 ui 是否是课程 vi 的直接或间接先决条件。我们创建一个 numCourses×numCourses 的矩阵 isPre,其中 isPre[x][y] 表示课程 x 是否是课程 y 的直接或间接先决条件,若是则 isPre[x][y] = True,否则 isPre[x][y] = False。在完成 isPre 计算后,我们对于每一个查询就可以在 O(1) 时间得到结果。对于 isPre 的计算,我们可以通过「广度优先搜索」+「拓扑排序」来对矩阵 isPre 进行计算:

首先我们需要计算有向图中每一个节点的入度,并对入度为 0 的节点加入队列。然后只要队列非空,就进行以下操作:

  • 取出队列队首元素,同时,将这个节点及其所有前置条件节点设置为所有后续节点的前置条件节点,然后对每一个后续节点入度进行 −1 操作,若操作后的节点入度为 0,则继续将该节点加入队列。

「拓扑排序」结束后,矩阵 isPre 计算完毕,然后我们遍历每一个查询,根据矩阵 isPre 即可得到每一个查询的结果。

代码:

class Solution {
public:vector<bool> checkIfPrerequisite(int numCourses, vector<vector<int>>& prerequisites, vector<vector<int>>& queries) {vector<vector<int>> g(numCourses);vector<int> indgree(numCourses, 0);vector<vector<bool>> isPre(numCourses, vector<bool>(numCourses, false));for (auto& p : prerequisites) {++indgree[p[1]];g[p[0]].push_back(p[1]);}queue<int> q;for (int i = 0; i < numCourses; ++i) {if (indgree[i] == 0) {q.push(i);}}while (!q.empty()) {auto cur = q.front();q.pop();for (auto& ne : g[cur]) {isPre[cur][ne] = true;for (int i = 0; i < numCourses; ++i) {isPre[i][ne] = isPre[i][ne] | isPre[i][cur];}--indgree[ne];if (indgree[ne] == 0) {q.push(ne);}}}vector<bool> res;for (auto& query : queries) {res.push_back(isPre[query[0]][query[1]]);}return res;}
};

时间 232ms 击败 46.33%使用 C++ 的用户
内存 58.08MB 击败 61.78%使用 C++ 的用户
复杂度分析

  • 时间复杂度:O(numCourses2+n+m),其中 numCourses 为课程数,n 为题目给出的先决条件的数目,m 为题目给出的查询数,其中通过计算矩阵 isPre 的时间复杂度为 O(numCourses2),构建有向图的复杂度为 O(numCourses+n),处理每一个查询的复杂度为 O(1),共有 m 个查询,所以总的查询时间复杂度为 O(m)。
  • 空间复杂度:O(numCourses2+n),其中 numCourses 为课程数,n 为题目给出的先决条件的数目,主要为构建有向图和矩阵 isPre 的空间开销。注意返回值不计入空间复杂度。

方法二:深度优先搜索 + 拓扑排序

思路与算法

「方法一」中「拓扑排序」的实现同样可以通过「深度优先搜索」来实现。与「广度优先搜索」计入每一个点的出度不同,通过「深度优先搜索」需要记录每一个点是否被访问,我们用 vi[x] 来表示课程 x 是否被访问,初始时为 False。

我们从编号小到大遍历全部节点,若节点 i 未被访问,则进入「深度优先搜索」流程:

  • 若当前节点 x 已被访问,则直接返回。
  • 若当前节点 x 未被访问,将访问状态设为已访问,然后继续对其全部后继节点递归进行「深度优先搜索」流程。将节点 x 置为其每一个后继节点 y 的先决条件,有 isPre[x][y] = True,以及对于每一个以 y 为先决条件的节点 t,节点 x 同样为 t 的先决条件,有 isPre[x][t] = True。

遍历完成后,「拓扑排序」完成,矩阵 isPre 计算完毕,然后我们遍历每一个查询,根据矩阵 isPre 即可得到每一个查询的结果。

代码:

class Solution {
public:void dfs(vector<vector<int>>& g, vector<vector<bool>>& isPre, vector<bool>& vi, int cur) {if (vi[cur]) {return;}vi[cur] = true;for (auto& ne : g[cur]) {dfs(g, isPre, vi, ne);isPre[cur][ne] = true;for (int i = 0; i < isPre.size(); ++i) {isPre[cur][i] = isPre[cur][i] | isPre[ne][i];}}}vector<bool> checkIfPrerequisite(int numCourses, vector<vector<int>>& prerequisites, vector<vector<int>>& queries) {vector<vector<int>> g(numCourses);vector<bool> vi(numCourses, false);vector<vector<bool>> isPre(numCourses, vector<bool>(numCourses, false));for (auto& p : prerequisites) {g[p[0]].push_back(p[1]);}for (int i = 0; i < numCourses; ++i) {dfs(g, isPre, vi, i);}vector<bool> res;for (auto& query : queries) {res.push_back(isPre[query[0]][query[1]]);}return res;}
};

时间 212ms 击败 55.98%使用 C++ 的用户
内存 57.84MB 击败 73.75%使用 C++ 的用户
复杂度分析

  • 时间复杂度:O(numCourses2+n+m) ,其中 numCourses 为课程数,n 为题目给出的先决条件的数目,m 为题目给出的查询数,其中计算矩阵 isPre 的时间复杂度为 O(numCourses2) ,构建有向图的复杂度为 O(numCourses+n),处理每一个查询的复杂度为 O(1),共有 m 个查询,所以总的查询时间复杂度为 O(m)。
  • 空间复杂度:O(numCourses2+n) ,其中 numCourses 为课程数,n 为题目给出的先决条件的数目,主要为构建有向图和矩阵 isPre 的空间开销。注意返回值不计入空间复杂度。
    author:力扣官方题解

相关文章:

【1462. 课程表 IV】

来源&#xff1a;力扣&#xff08;LeetCode&#xff09; 描述&#xff1a; 你总共需要上 numCourses 门课&#xff0c;课程编号依次为 0 到 numCourses-1 。你会得到一个数组 prerequisite &#xff0c;其中 prerequisites[i] [ai, bi] 表示如果你想选 bi 课程&#xff0c;你…...

Kerberos 身份验证

简介 Kerberos 是一种由 MIT&#xff08;麻省理工大学&#xff09;提出的一种基于加密 Ticket 的身份认证协议。它旨在通过使用密钥加密技术为客户端/服务器应用程序提供强身份验证&#xff0c;用于验证用户或主机的标识。。 适用范围&#xff1a;Windows Server 2022、Window…...

R语言贝叶斯METROPOLIS-HASTINGS GIBBS 吉布斯采样器估计变点指数分布分析泊松过程车站等待时间...

原文链接&#xff1a;http://tecdat.cn/?p26578 指数分布是泊松过程中事件之间时间的概率分布&#xff0c;因此它用于预测到下一个事件的等待时间&#xff0c;例如&#xff0c;您需要在公共汽车站等待的时间&#xff0c;直到下一班车到了&#xff08;点击文末“阅读原文”获取…...

通付盾入选2023年度“上市苗圃工程”重点企业

近日&#xff0c;2023年度苏州工业园区企业上市苗圃工程认定名单公示&#xff0c;江苏通付盾科技有限公司成功入选园区“上市苗圃工程”重点企业。 2023年第一批次苗圃企业认定结果&#xff1a; 企业上市苗圃工程 上市企业是衡量地方综合经济实力的重要标尺&#xff0c;也是区…...

SpringMVC之文件上传下载

SpringMVC是一个基于Java的Web框架&#xff0c;它提供了一套用于构建Web应用程序的开发模型。在SpringMVC中&#xff0c;文件上传和下载是常见的功能之一。 SpringMVC文件上传和下载的介绍&#xff1a; 介绍文件上传&#xff1a; 在SpringMVC中&#xff0c;文件上传功能可以通…...

嵌入式IDE(2):KEIL中SCF分散加载链接文件详解和实例分析

在上一篇文章IAR中ICF链接文件详解和实例分析中&#xff0c;我通过I.MX RT1170的SDK中的内存映射关系&#xff0c;分析了IAR中的ICF链接文件的语法。对于MCU编程所使用的IDE来说&#xff0c;IAR和Keil用得比较多&#xff0c;所以这一篇文章就来分析一下Keil的分散文件.scf(scat…...

Linux防火墙常用操作及端口开放

Linux防火墙常用操作及端口开放 1.查看防火墙状态 firewall-cmd --state 2.开启防火墙 systemctl start firewalld.service 3.开启指定端口 firewall-cmd --zonepublic --add-port3306/tcp --permanent firewall-cmd --zonepublic --add-port6379/tcp --permanent 显示success表…...

[JAVAee]Linux上的javax.mail报错

我们把在window写的项目部署到Linux上的Tomcat时,如果发现使用不了了,该如何找到错误呢?找到报错的地方在哪呢? 在Linux环境下来到Tomcat目录下的logs目录,输入: tail -f catalina.out -n 500 tail 就是把文件的末尾几行读取到终端上,并会持续刷新 -f 循环读取 catalina.ou…...

开学季|校园迎新哪家强?VR全景来导航

九月开学迎新季&#xff0c;各大高校的迎新活动开展的如火如荼&#xff0c;随着科技的不断进步&#xff0c;高校为了更好的开展迎新活动&#xff0c;让新生们尽快熟悉新的校园和生活&#xff0c;会利用VR全景技术带领着新生进行校园游览&#xff0c;给予新生们巨大便利的同时&a…...

el-checkbox-group限制勾选数量

<!--* Description: 视频监控 页面* Author: mhf* Date: 2023-08-15 13:26:33 --> <template><div class"videoSurveillance"><el-row :gutter"24"><el-col :span"4"><div class"videoSurveillance-left&…...

【JavaScript】WebAPI入门到实战

文章目录 一、WebAPI背景知识1. 什么是WebAPI&#xff1f;2. 什么是API&#xff1f; 二、DOM基本概念三、获取元素三、事件初识1. 点击事件2. 键盘事件 四、操作元素1. 获取/修改元素内容2. 获取/修改元素属性3. 获取/修改表单元素属性4. 获取/修改样式属性 五、操作节点1. 新增…...

奥康的高尔夫鞋,圈不住投资者的心

文 | 螳螂观察 作者 | 青月 鞋服行业终于熬过了“寒冬”&#xff0c;2023年行业景气度开始逐步回暖。 东方财富Choice数据显示&#xff0c;截至8月17日&#xff0c;已有28家鞋帽服装类上市公司发布了2023年中期业绩预告或快报&#xff0c;其中&#xff0c;9家预增&#xff0…...

vue2配置环境变量并且nginx运行成功

需求&#xff1a;我在vue项目配置了生产环境和开发环境&#xff0c;之后通过proxy代理的方式把地址转发到真实的服务器地址上用于请求接口&#xff0c;之后把项目打包后上传到nginx上&#xff0c;之后接口报错404&#xff0c;但是本地运行是可以访问的&#xff0c;找了很久终于…...

Java+Swing形成GUI图像界面

一、Swing 简介 Swing 主要用来开发 GUI 程序,GUI(Graphical User Interface)即图形用户界面。Java 中针对 GUI 设计提供了丰富的类库,这些类分别位于 java.awt 和 java.swing 中,简称 AWT 和 Swing ;其中,AWT(Abstract Window Toolkit)是抽象窗口工具包,是 Java 平…...

编辑距离 -- 动规

72. 编辑距离 给出动规的两种常见实现形式&#xff1a;自顶向下、自底向上&#xff0c;前者一般借助递归函数备忘录实现&#xff0c;后者通常基于dp数组实现。 class MinDistance:"""72. 编辑距离https://leetcode.cn/problems/edit-distance/""&quo…...

douyin【商品抢购js脚本】

文章目录 前言订阅须知知识点源码前言 脚本主要用来实现抢购douyin商城、直播间秒杀商品等一系列商品 订阅须知 订阅后,只提供js源代码,不提供教学,请根据源码自行抓包知识点 1、在查询串插入一个固定的键rstr   2、对查询串进行按键排序并取值,对空格和+进行转义为a …...

常见Web安全技术总结!474页Web安全从入门到精通(附PDF)

Web安全范围比较大&#xff0c;知识点比较杂&#xff0c;很多朋友都无从下手&#xff0c;这不可怕&#xff0c;可怕的是乱下手&#xff0c;其实往往基础才是决定你是否能走远的关键。 为了帮助大家入门网安&#xff0c;给大家推荐一份《新手Web安全入门到精通》&#xff0c;共…...

Prometheus 监控指南:如何可靠地记录数字时间序列数据

&#x1f337;&#x1f341; 博主猫头虎&#xff08;&#x1f405;&#x1f43e;&#xff09;带您 Go to New World✨&#x1f341; &#x1f405;&#x1f43e;猫头虎建议程序员必备技术栈一览表&#x1f4d6;&#xff1a; &#x1f6e0;️ 全栈技术 Full Stack: &#x1f4da…...

rsync远程同步+inotify监控

目录 一、Rsync 简介 1、rsync是什么 2、备份的方式 3、rsync同步方式 4、常用rsync命令 5、配置源的两种表达方法 二、rsync实验 1、本地复制 ​编辑​编辑 2、异地复制 2.1 rsync服务器配置 2.2 rsync客户端配置 2.2.1 普通同步 2.2.2 免密同步 2.2.3 --delet…...

【面试经典150 | 数组】移除元素

文章目录 写在前面Tag题目来源题目解读解题思路方法一&#xff1a;原地操作 写在最后 写在前面 本专栏专注于分析与讲解【面试经典150】算法&#xff0c;两到三天更新一篇文章&#xff0c;欢迎催更…… 专栏内容以分析题目为主&#xff0c;并附带一些对于本题涉及到的数据结构等…...

玩转Mysql系列 - 第21篇:什么是索引?

这是Mysql系列第21篇。 本文开始连续3篇详解mysql索引&#xff1a; 第1篇来说说什么是索引&#xff1f; 第2篇详解Mysql中索引的原理 第3篇结合索引详解关键字explain 本文为索引第一篇&#xff1a;我们来了解一下什么是索引&#xff1f; 路人在搞计算机之前&#xff0c;…...

预处理指令

// The include directive instructs the preprocessor to paste the text of the given file into the current file. // 粘贴指定文件的内容 #include // 定义宏PI #define PI 3.1415926 // 取消定义PI #undef PI条件编译(Conditional Compilation) // 检查xxx是否已被定义为…...

强大的JTAG边界扫描(1):基本原理介绍

文章目录 1. 什么是边界扫描&#xff1f;2. JTAG硬件接口3. 边界扫描相关的软硬件4. 学习资料5. 总结 我是怎么了解到边界扫描的呢&#xff1f; 这就要从我淘到一块FPGA板卡的事情说起了。 前段时间我在某二手平台上淘了一块FPGA板子&#xff0c;它长这样&#xff1a; 板子的…...

【C++】源文件.cpp和头文件.h分离编程

优势介绍 将C代码分为头文件&#xff08;.h&#xff09;和源文件&#xff08;.cpp&#xff09;的做法有以下几个好处&#xff1a; 模块化和代码组织&#xff1a;将函数和类的声明&#xff08;包括函数原型、类的成员和属性等&#xff09;放在头文件中&#xff0c;将函数和类的…...

报错ssh: Could not resolve hostname

…按照网上好多教程试了一下&#xff1a; 新建密钥&#xff0c;添加到gitee&#xff0c;重新测试。修改host&#xff0c;加入gitee的ip地址到里面去。修改.gifconfig配置文件&#xff0c;配置成ssh的仓库链接。 这上面的方法都不行&#xff0c;后面发现一篇文章&#xff1a;SS…...

从零开始学网站建设:从需求分析到上线发布

从零开始学网站建设&#xff1a;从需求分析到上线发布 一、需求分析 在进行网站建设之前&#xff0c;首先需要与客户进行沟通&#xff0c;了解客户的需求和要求&#xff0c;并进行深入的分析和研究。根据不同的需求&#xff0c;需要确定网站的类型、功能、布局、风格等方面的…...

软件系统验收测试需要注意的地方

验收测试 一、软件验收测试含义&#xff1a; 软件验收测试是指测试人员检验软件是否符合软件规格说明书和用户需求的测试活动。 验收测试是软件测试的最后一个环节&#xff0c;也是最为关键的一个要素。 它关系到软件开发公司的产品质量&#xff0c;也关系到需求方的产品能…...

解决three.js中加载纹理贴图时,初次渲染不显示的问题

效果&#xff1a; 解决方法&#xff1a;主要是将一些构建网格对象的操作放在了textureLoader.load()方法中&#xff0c;加载图片也用了require init() {// 1, 创建场景对象this.scene new this.$three.Scene();// 2, 创建立方缓冲几何体this.geometry new this.$three.BoxGe…...

Git学习记录

Contest 一、工作区域二、操作命令2.1 创建仓库2.2 查看仓库状态2.3 从工作区向暂存区添加文件2.3.1 只添加一个文件2.3.2 添加全部文件 2.4 从暂存区向仓库区添加文件2.5 查询日志2.5.1 从当前版本开始查询2.5.2 查看所有日志 2.6 回滚2.6.1 从仓库回滚到工作区2.6.2 取消工作…...

建筑模板木模好还是钢模好

在建筑施工中&#xff0c;模板是一项关键的工程&#xff0c;对于建筑结构的质量和施工效率起着重要作用。在选择模板材料时&#xff0c;木模和钢模都是常见的选择。本文将比较木模和钢模的优缺点&#xff0c;以帮助您做出明智的选择。 正文&#xff1a;一、木模&#xff1a;传统…...

网站怎么做排名呢/目前小说网站排名

css实现水平垂直居中的七种方式一、使用grid布局二、使用flex布局三、使用定位外边距四、使用定位平移五、使用外边距 平移六、使用文本对齐 行高七、使用表格单元一、使用grid布局 <!DOCTYPE html> <html lang"en"><head><title>test<…...

移动版wordpress主题/怎么在百度上发表文章

当手机中的应用越来越多、绑定的服务也越来越多时&#xff0c;谁会想到一条短信引发的连锁反应&#xff0c;能让一个人在一夜间倾家荡产&#xff1f;近日&#xff0c;北京许先生的遭遇《中国移动&#xff0c;请你告诉我&#xff0c;为什么一条短信就能骗走我所有的财产&#xf…...

南昌模板建站定制/seo方案

从Npm Script到Webpack&#xff0c;6种常见的前端构建工具对比 小编说&#xff1a;历史上先后出现了一系列构建工具&#xff0c;它们各有优缺点。由于前端工程师很熟悉JavaScript&#xff0c;Node.js又可以胜任所有构建需求&#xff0c;所以大多数构建工具都是用Node.js开发的。…...

西安网站开发费用/seo优化神器

一&#xff0c;简单介绍&#xff1a;防火墙防火墙&#xff08;Firewall&#xff09;是一项协助确保信息安全的设备&#xff0c;会依照特定的规则&#xff0c;允许或是限制传输的数据通过。防火墙可以是一台专属的硬件也可以是架设在一般硬件上的一套软件。防火墙是用来阻挡外部…...

十年网站建设/重庆黄埔seo整站优化

题目相关 题目链接 洛谷&#xff0c;https://www.luogu.com.cn/problem/P1114。 计蒜客&#xff0c;https://nanti.jisuanke.com/t/T1853。 我的OJ&#xff0c;http://47.110.135.197/problem.php?id5252。 题目描述 近来&#xff0c;初一年的XXX小朋友致力于研究班上同…...

做计算机网站的总结/惠州网站推广排名

目前深度图像的获取方法有激光雷达深度成像法&#xff0c;计算机立体视觉成像&#xff0c;坐标测量机法&#xff0c;莫尔条纹法&#xff0c;结构光法等等&#xff0c;针对深度图像的研究重点主要集中在以下几个方面&#xff0c;深度图像的分割技术 &#xff0c;深度图像的边缘检…...