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

news/2025/2/18 10:37:55/

(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…