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

华为OD机试真题 Java 实现【快速开租建站】【2023Q1 200分】,附详细解题思路

一、题目描述

当前IT部门支撑了子公司颗粒化业务,该部门需要实现为子公司快速开租建站的能力,建站是指在一个全新的环境部署一套IT服务。

每个站点开站会由一系列部署任务项构成,每个任务项部署完成时间都是固定和相等的,设为1。部署任务项之间可能存在依赖,假如任务2依赖任务1,那么等任务1部署完,任务2才能部署。任务有多个依赖任务则需要等所有依赖任务都部署完该任务才能部署。

没有依赖的任务可以并行部署,优秀的员工们会做到完全并行无等待的部署。

给定一个站点部署任务项和它们之间的依赖关系,请给出一个站点的最短开站时间。

二、输入描述

第一行是任务数taskNum,第二行是任务的依赖关系数relationsNum接下来 relationsNum 行,每行包含两个id,描述一个依赖关系,格式为: Di Dj,表示部署任务部署完成了,部署任务j才能部署,IDi 和IDj 值的范围为: [0,taskNum)注:输入保证部署任务之间的依赖不会存在环。

三、输出描述

1个整数,表示一个站点的最短开站时间。

四、解题思路

  1. 创建map,用于存储任务之间的依赖关系,key为任务编号,value为依赖该任务的任务列表;
  2. 循环读取num数据,将依赖关系存储map;
  3. 创建一个长度为n的数组,存储每个任务的最小启动时间;
  4. 创建变量time,用于记录最短开站时间;
  5. 递归调用,计算任务的最小启动时间;
  6. 如果当前任务没有依赖,表示该任务可以立即启动,将其最小启动时间设置为1,并返回1,停止递归;
  7. 遍历当前任务依赖的任务列表,递归调用getMinTime函数来获取依赖任务的最小启动时间,取其中的最大值作为当前任务的最小启动时间minDependTime;
  8. 当前任务的最小启动时间为依赖任务的最小启动时间加1,将该值记录到timeArr数组中,并返回该值;
  9. 输出最短开站时间time;

五、Java算法源码

public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = Integer.parseInt(sc.nextLine());int num = Integer.parseInt(sc.nextLine());// 1、创建map,用于存储任务之间的依赖关系,key为任务编号,value为依赖该任务的任务列表Map<Integer, List<Integer>> map = new HashMap<>();// 2、循环读取num数据,将依赖关系存储mapfor (int i = 0; i < num; i++) {String line = sc.nextLine();String[] arr = line.split(" ");int left = Integer.parseInt(arr[0]);int right = Integer.parseInt(arr[1]);List<Integer> list = map.getOrDefault(left, new ArrayList<>());list.add(right);map.put(left, list);}// 3、创建一个长度为n的数组,存储每个任务的最小启动时间int[] timeArr = new int[n];// 4、创建变量time,用于记录最短开站时间int time = 0;for (int i = 0; i < n; i++) {// 5、递归调用,计算任务的最小启动时间int needTime = getMinTime(i, map, timeArr);time = Math.max(time, needTime);}// 9、输出最短开站时间timeSystem.out.println(time);
}/**** @param index 当前位置* @param map 输入的数据集合* @param timeArr 任务时间* @return*/
public static int getMinTime(int index, Map<Integer, List<Integer>> map, int[] timeArr) {List<Integer> list = map.getOrDefault(index, new ArrayList<>());// 6、如果当前任务没有依赖,表示该任务可以立即启动,将其最小启动时间设置为1,并返回1,停止递归if (list.size() == 0) {//最小启动时间timeArr[index] = 1;return 1;}int minDependTime = Integer.MIN_VALUE;// 7、遍历当前任务依赖的任务列表,递归调用getMinTime函数来获取依赖任务的最小启动时间,// 取其中的最大值作为当前任务的最小启动时间minDependTimefor (int taskNum : list) {// 通过递归取最小启动时间if (timeArr[taskNum] == 0) {timeArr[taskNum] = getMinTime(taskNum, map, timeArr);}minDependTime = Math.max(minDependTime, timeArr[taskNum]);}// 8、当前任务的最小启动时间为依赖任务的最小启动时间加1,将该值记录到timeArr数组中,并返回该值int needTime = minDependTime + 1;timeArr[index] = needTime;return needTime;
}

六、效果展示

1、输入

5
5
0 4
1 2
1 3
2 3
2 4

2、输出

3

3、说明

有5个部署任务项,5个依赖关系,如下图所示。我们可以先同时部署任务项0和任务项1,然后部署任务项2,最后同时部署任务项3和任务项4。最短开站时间为3。

在这里插入图片描述


🏆下一篇:华为OD机试真题 Java 实现【获得完美走位】【2023Q1 100分】

🏆本文收录于,华为OD机试(JAVA)(2022&2023)

本专栏包含了最新最全的2023年华为OD机试真题,有详细的分析和Java解答。已帮助1000+同学顺利通过OD机考。专栏会持续更新,每天在线答疑。

在这里插入图片描述

相关文章:

华为OD机试真题 Java 实现【快速开租建站】【2023Q1 200分】,附详细解题思路

一、题目描述 当前IT部门支撑了子公司颗粒化业务&#xff0c;该部门需要实现为子公司快速开租建站的能力&#xff0c;建站是指在一个全新的环境部署一套IT服务。 每个站点开站会由一系列部署任务项构成&#xff0c;每个任务项部署完成时间都是固定和相等的&#xff0c;设为1。…...

照片中对象识别模型YOLOv3在iOS项目中的浅析与使用

本文所指的YOLOv3模型为苹果开发者官网提供的图形识别对象的CoreML模型&#xff0c;可识别80种对象&#xff0c;并给出识别的对象在图形中的位置和大小信息。 我们可以直接在官网下载该模型&#xff1a; 机器学习 - 模型 - Apple Developer 然后直接将模型拖入工程中&#x…...

Caffeine 本地高速缓存工具类

目录 Caffeine工具类方式 SpringBoot 整合 Caffeine 缓存 &#xff08;SpringCache模式&#xff09; 驱逐策略 开发使用 Caffeine是一种高性能的缓存库&#xff0c;是基于Java 8的最佳&#xff08;最优&#xff09;缓存框架&#xff0c;性能各方面优于guava。 Caffeine工具…...

加密解密软件VMProtect教程(八)许可制度之序列号生成器

VMProtect是新一代软件保护实用程序。VMProtect支持德尔菲、Borland C Builder、Visual C/C、Visual Basic&#xff08;本机&#xff09;、Virtual Pascal和XCode编译器。 同时&#xff0c;VMProtect有一个内置的反汇编程序&#xff0c;可以与Windows和Mac OS X可执行文件一起…...

单源最短路的建图

1.热浪 信息学奥赛一本通&#xff08;C版&#xff09;在线评测系统 (ssoier.cn)http://ybt.ssoier.cn:8088/problem_show.php?pid1379 很裸的单源最短路问题&#xff0c;n2500,可以用dijksta或者spfa都能过&#xff0c;下面展示spfa的做法 #include<bits/stdc.h> usi…...

MyBatis基本操作及SpringBoot单元测试

目录 一、什么是单元测试&#xff1f; 1.1 单元测试的好处 1.2 单元测试的实现步骤 1.2.1 生成单元测试类&#xff1a; 1.2.2 SpringBootTest注解 1.2.3 检验方法结果&#xff1a; 二、利用MyBatis实现查询操作 2.1单表查询 2.2 参数占位符 #{} 和 ${} 2.2.1 ${} 字符…...

Linux之创建进程、查看进程、进程的状态以及进程的优先级

文章目录 前言一、初识fork1.演示2.介绍3.将子进程与父进程执行的任务分离4.多进程并行 二、进程的状态1.进程的状态都有哪些&#xff1f;2.查看进程的状态2.运行&#xff08;R&#xff09;3.阻塞4.僵尸进程&#xff08;Z&#xff09;1.僵尸状态概念2.为什么要有僵尸状态&#…...

k8s部署rabbitmq

docker pull rabbitmq:3.9.28-management 1.部署模板 apiVersion: v1 kind: Service metadata:name: rabbitmq spec:ports:- name: amqpport: 5672targetPort: 5672- name: managementport: 15672targetPort: 15672selector:app: rabbitmq---apiVersion: apps/v1 kind: Statef…...

关于QGroundControl的软件架构的理解

首先QGC是基于QT平台开发&#xff0c;个人理解软件架构即为项目前后端结构&#xff0c;以及前后端数据交互的逻辑。下面是对QGroundControl源码的一些个人理解&#xff0c;写这个博客只是为了记录下来&#xff0c;防止时间久了忘记&#xff0c;过程中看了一些大佬的博客来帮助理…...

Android 文本识别:MLKIT + PreviewView

随着移动设备的普及和摄像头的高像素化&#xff0c;利用相机进行文本识别成为了一种流行的方式。MLKit 是 Google 提供的一款机器学习工具包&#xff0c;其中包含了丰富的图像和语言处理功能&#xff0c;包括文本识别。PreviewView 是 Android Jetpack 的一部分&#xff0c;它提…...

刮泥机的分类有哪些及组成部分

刮泥机的分类有哪些及组成部分 刮泥机的分类&#xff1a; 刮泥机主要包括&#xff1a;周边传动刮泥机、中心传动浓缩刮泥机。 1、中心传动浓缩刮泥机&#xff1a;主要由溢流装置、大梁及拦杆、进口管、传动装置、电器箱、稳流筒、主轴、浮渣耙板、刮集装置、水下轴承、小刮刀、…...

Qt编程基础 | 第六章-窗体 | 6.2、VS导入资源文件

一、VS导入资源文件 1.1、导入资源文件 步骤一&#xff1a; 将所有图片放到各自文件夹下&#xff0c;并将文件夹拷贝到资源文件&#xff08;.qrc文件&#xff09;的同级目录下&#xff0c;如下&#xff1a; 步骤二&#xff1a; 新建VS项目的时候&#xff0c;系统会自动建好一…...

NET框架程序设计-第4章类型基础

4.1 所有类型的基类型&#xff1a;System.Object CLR 要求每个类型最终都要继承自 System.Object 类型。 两种类型定义&#xff1a; 1&#xff09;隐式继承 //隐式继承 Object class Employee{}2&#xff09;显式继承 class Employee:System.Object{}System.Object 主要的公…...

Java设计模式-备忘录模式

简介 在软件开发中&#xff0c;设计模式是为了解决常见问题而提出的一种经过验证的解决方案。备忘录模式&#xff08;Memento Pattern&#xff09;是一种行为型设计模式&#xff0c;它允许我们在不破坏封装性的前提下&#xff0c;捕获和恢复对象的内部状态。 备忘录模式是一种…...

Zookeeper集群 + Kafka集群

Zookeeper 概述 Zookeeper 定义 Zookeeper是一个开源的分布式的&#xff0c;为分布式框架提供协调服务的Apache项目。 Zookeeper 工作机制 Zookeeper从设计模式角度来理解&#xff1a;是一个基于观察者模式设计的分布式服务管理框架&#xff0c;它负责存储和管理大家都关心的数…...

“邮件营销新趋势,这个平台让你收获颇丰!

随着各媒体平台的迅速发展&#xff0c;2023年大家更专注于视频营销、网红营销、直播营销等营销方式。可以见得&#xff0c;数字媒介手段的发展&#xff0c;对于营销方式也产生了巨大的影响。但是&#xff0c;企业在拥抱新兴的营销方式的同时&#xff0c;也不要忽视传统的营销方…...

Python列表推导

列表推导式 列表推导式创建列表的方式更简洁。常见的用法为&#xff0c;对序列或可迭代对象中的每个元素应用某种操作&#xff0c;用生成的结果创建新的列表&#xff1b;或用满足特定条件的元素创建子序列。 例如&#xff0c;创建平方值的列表&#xff1a; squares [] for …...

git使用查看分支、创建分支、合并分支

一、查看分支 查看的git命令如下&#xff1a; git branch 列出本地已经存在的分支&#xff0c;并且当前分支会用*标记 git branch -r 查看远程版本库的分支列表 git branch -a 查看所有分支列表&#xff08;包括本地和远程&#xff0c;remotes/开头的表示远程分支&#xff09;…...

vue3.0与vue2.0

一、生命周期的变化 1.vue2.响应式架构 2.vue3.0 响应式架构图 Vue3.0响应式框架在设计上&#xff0c;将视图渲染和数据响应式完全分离开来。将响应式核心方法effect从原有的Watcher中抽离。这样&#xff0c;当我们只需要监听数据响应某种逻辑回调(例如监听某个text属性的变化…...

HTML 中的常用标签用法

HTML是构建Web页面的基础语言&#xff0c;其中包含许多不同类型的标签。这些标签由尖括号包围&#xff0c;以指示浏览器如何呈现文本。下面是HTML中的一些常用标签以及它们的使用方法&#xff1a; 标题标签&#xff08;h1-h6&#xff09; 标题标签用于标识页面内容的标题&…...

多模态2025:技术路线“神仙打架”,视频生成冲上云霄

文&#xff5c;魏琳华 编&#xff5c;王一粟 一场大会&#xff0c;聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中&#xff0c;汇集了学界、创业公司和大厂等三方的热门选手&#xff0c;关于多模态的集中讨论达到了前所未有的热度。其中&#xff0c;…...

利用ngx_stream_return_module构建简易 TCP/UDP 响应网关

一、模块概述 ngx_stream_return_module 提供了一个极简的指令&#xff1a; return <value>;在收到客户端连接后&#xff0c;立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量&#xff08;如 $time_iso8601、$remote_addr 等&#xff09;&a…...

【Linux】C语言执行shell指令

在C语言中执行Shell指令 在C语言中&#xff0c;有几种方法可以执行Shell指令&#xff1a; 1. 使用system()函数 这是最简单的方法&#xff0c;包含在stdlib.h头文件中&#xff1a; #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...

深入理解JavaScript设计模式之单例模式

目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式&#xff08;Singleton Pattern&#…...

MySQL中【正则表达式】用法

MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现&#xff08;两者等价&#xff09;&#xff0c;用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例&#xff1a; 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...

自然语言处理——循环神经网络

自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元&#xff08;GRU&#xff09;长短期记忆神经网络&#xff08;LSTM&#xff09…...

代理篇12|深入理解 Vite中的Proxy接口代理配置

在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...

【数据分析】R版IntelliGenes用于生物标志物发现的可解释机器学习

禁止商业或二改转载&#xff0c;仅供自学使用&#xff0c;侵权必究&#xff0c;如需截取部分内容请后台联系作者! 文章目录 介绍流程步骤1. 输入数据2. 特征选择3. 模型训练4. I-Genes 评分计算5. 输出结果 IntelliGenesR 安装包1. 特征选择2. 模型训练和评估3. I-Genes 评分计…...

在Mathematica中实现Newton-Raphson迭代的收敛时间算法(一般三次多项式)

考察一般的三次多项式&#xff0c;以r为参数&#xff1a; p[z_, r_] : z^3 (r - 1) z - r; roots[r_] : z /. Solve[p[z, r] 0, z]&#xff1b; 此多项式的根为&#xff1a; 尽管看起来这个多项式是特殊的&#xff0c;其实一般的三次多项式都是可以通过线性变换化为这个形式…...

jdbc查询mysql数据库时,出现id顺序错误的情况

我在repository中的查询语句如下所示&#xff0c;即传入一个List<intager>的数据&#xff0c;返回这些id的问题列表。但是由于数据库查询时ID列表的顺序与预期不一致&#xff0c;会导致返回的id是从小到大排列的&#xff0c;但我不希望这样。 Query("SELECT NEW com…...