# (1462. 课程表 IV leetcode)广搜+拓扑-------------------Java实现

news/2024/2/28 10:08:27

(1462. 课程表 IV leetcode)广搜+拓扑-------------------Java实现

题目表述

你总共需要上 numCourses 门课,课程编号依次为 0 到 numCourses-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 个查询的答案。

样例

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

条件

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

思路

1、广搜+拓扑,暴力解法,其实可以把数据结构由hashset变成二维数组记录,这样会省时间空间
建议再做一边。

注意点

ac代码

Java方法一:

class Solution {public List<Boolean> checkIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries) {HashSet<Integer> SourceToTarget[] = new HashSet[numCourses];HashSet<Integer> BeforeSource[] = new HashSet[numCourses];int source[] = new int[numCourses];List<Boolean> result = new ArrayList<>();for (int i=0;i<numCourses;i++) {SourceToTarget[i] = new HashSet<>();BeforeSource[i] = new HashSet<>();}for (int[] node:prerequisites)if (!SourceToTarget[node[0]].contains(node[1])) {source[node[1]]++;SourceToTarget[node[0]].add(node[1]);BeforeSource[node[1]].add(node[0]);}Queue<Integer> q = new LinkedList<>();for (int i = 0;i<numCourses;i++)if (source[i]==0)q.offer(i);while(!q.isEmpty()){int now = q.poll();for (Integer target:SourceToTarget[now]){source[target]--;if (source[target]==0)q.offer(target);for (Integer s:BeforeSource[now])if (!BeforeSource[target].contains(s))BeforeSource[target].add(s);}}for(int i=0;i<numCourses;i++){for (int s:BeforeSource[i])System.out.print(s+" ");System.out.println();}//judgefor (int i=0;i<queries.length;i++)if(BeforeSource[queries[i][1]].contains(queries[i][0]))result.add(Boolean.TRUE);elseresult.add(Boolean.FALSE);return result;}
}

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/squares-of-a-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


http://www.ppmy.cn/news/1107679.html

相关文章

vue3之pinia简单使用

一、 Pinia介绍 pinia 是 Vue 的存储库&#xff0c;它允许您跨组件/页面共享状态。就是和vuex一样的实现数据共享。 依据Pinia官方文档&#xff0c;Pinia是2019年由vue.js官方成员重新设计的新一代状态管理器&#xff0c;更替Vuex4成为Vuex5。 Pinia 目前也已经是 vue 官方正式…

手搭手入门MybaitsX

Mybatis-Plus介绍 为简化开发而生 MyBatis-Plus(opens new window)&#xff08;简称 MP&#xff09;是一个 MyBatis(opens new window) 的增强工具&#xff0c;在 MyBatis 的基础上只做增强不做改变&#xff0c;为简化开发、提高效率而生。 特性 无侵入&#xff1a;只做增强…

C++QT day 5

实现一个图形类&#xff08;Shape&#xff09;&#xff0c;包含受保护成员属性&#xff1a;周长、面积&#xff0c; 公共成员函数&#xff1a;特殊成员函数书写 定义一个圆形类&#xff08;Circle&#xff09;&#xff0c;继承自图形类&#xff0c;包含私有属性&#xff1a;半…

绝热量热法反应热测试过程中的温度和压力自动跟踪控制解决方案

摘要&#xff1a;现有的ARC加速量热仪普遍存在单热电偶温差测量误差大造成绝热效果不好&#xff0c;以及样品球较大壁厚造成热惰性因子较大&#xff0c;都使得ARC测量精度不高。为此本文提出了技术改进解决方案&#xff0c;一是采用多只热电偶组成的温差热电堆进行温差测量&…

3基于MATLAB的齿轮啮合仿真,可根据需要调节齿轮参数,实现齿轮啮合转动动态过程。程序已调通,可直接运行。

基于MATLAB的齿轮啮合仿真&#xff0c;可根据需要调节齿轮参数&#xff0c;实现齿轮啮合转动动态过程。程序已调通&#xff0c;可直接运行。 3matlab齿轮啮合仿真动态啮合 (xiaohongshu.com)

c语言对特定位置0,置1

//将特定位置1 //参数1 数值 参数2 要置1的位 void set_biti(int *num, int pos) {*num | (1 << pos); }//将特定位置0 //参数1 数值 参数2 要置0的位 void clear_biti(int *num, int pos) {*num & ~(1 << pos); }#include <stdio.h> void set_biti(int …

【LeetCode题目详解】第九章 动态规划part17 647. 回文子串 ● 516.最长回文子序列(day57补)

本文章代码以c为例&#xff01; 一、力扣第647题&#xff1a;回文子串 题目&#xff1a; 给你一个字符串 s &#xff0c;请你统计并返回这个字符串中 回文子串 的数目。 回文字符串 是正着读和倒过来读一样的字符串。 子字符串 是字符串中的由连续字符组成的一个序列。 具…

Redis模块一:缓存简介

目录 缓存的定义 应用 生活案例 程序中的缓存 缓存优点 缓存的定义 缓存是⼀个高速数据交换的存储器&#xff0c;使用它可以快速的访问和操作数据。 应用 1.CPU缓存&#xff1a;CPU缓存是位于CPU和内存之间的临时存储器&#xff0c;它的容量通常远小于内存&#xff0…

第4章_freeRTOS入门与工程实践之开发板使用

本教程基于韦东山百问网出的 DShanMCU-F103开发板 进行编写&#xff0c;需要的同学可以在这里获取&#xff1a; https://item.taobao.com/item.htm?id724601559592 配套资料获取&#xff1a;https://rtos.100ask.net/zh/freeRTOS/DShanMCU-F103 freeRTOS系列教程之freeRTOS入…

图书管理系统 数据结构先导课暨C语言大作业复习 | JorbanS

问题描述 读取给定的图书文件book.txt中的信息&#xff08;book.txt中部分图书信息如下图所示&#xff09;&#xff0c;完成一个图书信息管理系统&#xff0c;该系统的各个功能模块要求利用菜单选项进行选择。 系统功能要求 图书浏览 读取book.txt中的文件信息并依次输出所…

【面试题精讲】你知道MySQL中有哪些隔离级别吗

uuid: 7ae741a0-517a-11ee-93e3-6f2b73edb0c7 title: 【面试题精讲】你知道MySQL中有哪些隔离级别吗 tags: [MySQL, 隔离级别, 脏读, 幻读, 不可重复读] categories: [技术文章, 后端技术, 系列文章, 面试题精讲] abbrlink: 14595062 date: 2023-09-12 22:41:38 有时博客内容会…

OpenCV学习笔记(6)_由例程学习高斯图像金字塔和拉普拉斯金字塔

1 图像金字塔 图像金字塔是图像多尺度表达的一种。 尺度&#xff0c;顾名思义&#xff0c;可以理解为图像的尺寸和分辨率。处理图像时&#xff0c;经常对源图像的尺寸进行缩放变换&#xff0c;进而变换为适合我们后续处理的大小的目标图像。这个对尺寸进行放大缩小的变换过程…

Visual Studio将C#项目编译成EXE可执行程序

经常看文章时会收获不少实用工具&#xff0c;有的在github上是编译好的&#xff0c;有的则是未编译的项目文件。所以经常会使用Visual Studio编译项目文件成exe可执行程序&#xff0c;以下为编译的流程。 第一步&#xff0c;从github上下载项目文件&#xff0c;举个例子&#…

Pytorch 多卡并行(2)—— 使用 torchrun 进行容错处理

前文 Pytorch 多卡并行&#xff08;1&#xff09;—— 原理简介和 DDP 并行实践 介绍了使用 Pytorch 的 DDP 库进行单机多卡训练的方法&#xff0c;本文进一步说明如何用 torchrun 改写前文代码&#xff0c;以提高模型训练的效率和容错性torchrun 是从 Pytorch 1.9.0 开始引入的…

使用Langchain+GPT+向量数据库chromadb 来创建文档对话机器人

使用LangchainGPT向量数据库chromadb 来创建文档对话机器人 一.效果图如下&#xff1a; 二.安装包 pip install langchainpip install chromadbpip install unstructuredpip install jieba三.代码如下 #!/usr/bin/python # -*- coding: UTF-8 -*-import os # 导入os模块&…

python中的小tips

1、注释 1、注释快捷键&#xff1a; Ctrl/ 可以注释掉光标所在的这一行&#xff0c;或者是选中的区域。 对于注释掉的这一行或者这一区域&#xff0c;按下ctrl/则会去掉注释。 2、多行注释 在写多行注释时&#xff0c;英文状态下写三个"&#xff0c;会自动变成六个"&…

kettle连接达梦资源库-达梦资源库初始化SQL

kettle连接达梦资源库经常性出现连接成功&#xff0c;但是未自动初始化SQL。所以这里特地提供可用的SQL。本人已经在DM8内亲测成功&#xff0c;已正常使用。 直接上文&#xff08;复制SQL语句&#xff0c;直接在达梦数据库运行即可&#xff09;&#xff1a; create table R_CL…

掌动智能分享:性能压力测试的重要性与优势

在当今数字化时代&#xff0c;应用程序的性能对于用户体验和业务成功至关重要。为了保证应用程序的高性能和稳定性&#xff0c;性能压力测试成为了不可或缺的环节。在这个领域&#xff0c;掌动智能作为一家专业的性能压力测试公司&#xff0c;正以其卓越的技术与服务&#xff0…

【C++基础】5. 常量

文章目录 【 1. 常量的分类 】1.1 整型常量1.2 浮点常量1.3 字符常量1.4 字符串常量1.5 布尔常量 【 2. 常量的定义 】2.1 #define 预处理器2.2 const 关键字 常量 是固定值&#xff0c;在程序执行期间不会改变。这些固定的值&#xff0c;又叫做字面量。常量可以是任何的基本数…

自动创建设备节点udev机制实现

自动创建设备节点udev机制实现过程&#xff1a; 1.当插入设备&#xff0c;内核会向udev发送一个事件&#xff0c;其中包含着设备的信息。 2.udev会根据收到的设备信息匹配相应的规则文件。 3.udev会根据规则文件中的配置&#xff0c;创建一个唯一的设备节点文件。通常存储在/d…
最新文章