华为OD机试真题 Java 实现【快速开租建站】【2023Q1 200分】,附详细解题思路
一、题目描述
当前IT部门支撑了子公司颗粒化业务,该部门需要实现为子公司快速开租建站的能力,建站是指在一个全新的环境部署一套IT服务。
每个站点开站会由一系列部署任务项构成,每个任务项部署完成时间都是固定和相等的,设为1。部署任务项之间可能存在依赖,假如任务2依赖任务1,那么等任务1部署完,任务2才能部署。任务有多个依赖任务则需要等所有依赖任务都部署完该任务才能部署。
没有依赖的任务可以并行部署,优秀的员工们会做到完全并行无等待的部署。
给定一个站点部署任务项和它们之间的依赖关系,请给出一个站点的最短开站时间。
二、输入描述
第一行是任务数taskNum,第二行是任务的依赖关系数relationsNum接下来 relationsNum 行,每行包含两个id,描述一个依赖关系,格式为: Di Dj,表示部署任务部署完成了,部署任务j才能部署,IDi 和IDj 值的范围为: [0,taskNum)注:输入保证部署任务之间的依赖不会存在环。
三、输出描述
1个整数,表示一个站点的最短开站时间。
四、解题思路
- 创建map,用于存储任务之间的依赖关系,key为任务编号,value为依赖该任务的任务列表;
- 循环读取num数据,将依赖关系存储map;
- 创建一个长度为n的数组,存储每个任务的最小启动时间;
- 创建变量time,用于记录最短开站时间;
- 递归调用,计算任务的最小启动时间;
- 如果当前任务没有依赖,表示该任务可以立即启动,将其最小启动时间设置为1,并返回1,停止递归;
- 遍历当前任务依赖的任务列表,递归调用getMinTime函数来获取依赖任务的最小启动时间,取其中的最大值作为当前任务的最小启动时间minDependTime;
- 当前任务的最小启动时间为依赖任务的最小启动时间加1,将该值记录到timeArr数组中,并返回该值;
- 输出最短开站时间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部门支撑了子公司颗粒化业务,该部门需要实现为子公司快速开租建站的能力,建站是指在一个全新的环境部署一套IT服务。 每个站点开站会由一系列部署任务项构成,每个任务项部署完成时间都是固定和相等的,设为1。…...
照片中对象识别模型YOLOv3在iOS项目中的浅析与使用
本文所指的YOLOv3模型为苹果开发者官网提供的图形识别对象的CoreML模型,可识别80种对象,并给出识别的对象在图形中的位置和大小信息。 我们可以直接在官网下载该模型: 机器学习 - 模型 - Apple Developer 然后直接将模型拖入工程中&#x…...
Caffeine 本地高速缓存工具类
目录 Caffeine工具类方式 SpringBoot 整合 Caffeine 缓存 (SpringCache模式) 驱逐策略 开发使用 Caffeine是一种高性能的缓存库,是基于Java 8的最佳(最优)缓存框架,性能各方面优于guava。 Caffeine工具…...
加密解密软件VMProtect教程(八)许可制度之序列号生成器
VMProtect是新一代软件保护实用程序。VMProtect支持德尔菲、Borland C Builder、Visual C/C、Visual Basic(本机)、Virtual Pascal和XCode编译器。 同时,VMProtect有一个内置的反汇编程序,可以与Windows和Mac OS X可执行文件一起…...
单源最短路的建图
1.热浪 信息学奥赛一本通(C版)在线评测系统 (ssoier.cn)http://ybt.ssoier.cn:8088/problem_show.php?pid1379 很裸的单源最短路问题,n2500,可以用dijksta或者spfa都能过,下面展示spfa的做法 #include<bits/stdc.h> usi…...
MyBatis基本操作及SpringBoot单元测试
目录 一、什么是单元测试? 1.1 单元测试的好处 1.2 单元测试的实现步骤 1.2.1 生成单元测试类: 1.2.2 SpringBootTest注解 1.2.3 检验方法结果: 二、利用MyBatis实现查询操作 2.1单表查询 2.2 参数占位符 #{} 和 ${} 2.2.1 ${} 字符…...
Linux之创建进程、查看进程、进程的状态以及进程的优先级
文章目录 前言一、初识fork1.演示2.介绍3.将子进程与父进程执行的任务分离4.多进程并行 二、进程的状态1.进程的状态都有哪些?2.查看进程的状态2.运行(R)3.阻塞4.僵尸进程(Z)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平台开发,个人理解软件架构即为项目前后端结构,以及前后端数据交互的逻辑。下面是对QGroundControl源码的一些个人理解,写这个博客只是为了记录下来,防止时间久了忘记,过程中看了一些大佬的博客来帮助理…...
Android 文本识别:MLKIT + PreviewView
随着移动设备的普及和摄像头的高像素化,利用相机进行文本识别成为了一种流行的方式。MLKit 是 Google 提供的一款机器学习工具包,其中包含了丰富的图像和语言处理功能,包括文本识别。PreviewView 是 Android Jetpack 的一部分,它提…...
刮泥机的分类有哪些及组成部分
刮泥机的分类有哪些及组成部分 刮泥机的分类: 刮泥机主要包括:周边传动刮泥机、中心传动浓缩刮泥机。 1、中心传动浓缩刮泥机:主要由溢流装置、大梁及拦杆、进口管、传动装置、电器箱、稳流筒、主轴、浮渣耙板、刮集装置、水下轴承、小刮刀、…...
Qt编程基础 | 第六章-窗体 | 6.2、VS导入资源文件
一、VS导入资源文件 1.1、导入资源文件 步骤一: 将所有图片放到各自文件夹下,并将文件夹拷贝到资源文件(.qrc文件)的同级目录下,如下: 步骤二: 新建VS项目的时候,系统会自动建好一…...
NET框架程序设计-第4章类型基础
4.1 所有类型的基类型:System.Object CLR 要求每个类型最终都要继承自 System.Object 类型。 两种类型定义: 1)隐式继承 //隐式继承 Object class Employee{}2)显式继承 class Employee:System.Object{}System.Object 主要的公…...
Java设计模式-备忘录模式
简介 在软件开发中,设计模式是为了解决常见问题而提出的一种经过验证的解决方案。备忘录模式(Memento Pattern)是一种行为型设计模式,它允许我们在不破坏封装性的前提下,捕获和恢复对象的内部状态。 备忘录模式是一种…...
Zookeeper集群 + Kafka集群
Zookeeper 概述 Zookeeper 定义 Zookeeper是一个开源的分布式的,为分布式框架提供协调服务的Apache项目。 Zookeeper 工作机制 Zookeeper从设计模式角度来理解:是一个基于观察者模式设计的分布式服务管理框架,它负责存储和管理大家都关心的数…...
“邮件营销新趋势,这个平台让你收获颇丰!
随着各媒体平台的迅速发展,2023年大家更专注于视频营销、网红营销、直播营销等营销方式。可以见得,数字媒介手段的发展,对于营销方式也产生了巨大的影响。但是,企业在拥抱新兴的营销方式的同时,也不要忽视传统的营销方…...
Python列表推导
列表推导式 列表推导式创建列表的方式更简洁。常见的用法为,对序列或可迭代对象中的每个元素应用某种操作,用生成的结果创建新的列表;或用满足特定条件的元素创建子序列。 例如,创建平方值的列表: squares [] for …...
git使用查看分支、创建分支、合并分支
一、查看分支 查看的git命令如下: git branch 列出本地已经存在的分支,并且当前分支会用*标记 git branch -r 查看远程版本库的分支列表 git branch -a 查看所有分支列表(包括本地和远程,remotes/开头的表示远程分支)…...
vue3.0与vue2.0
一、生命周期的变化 1.vue2.响应式架构 2.vue3.0 响应式架构图 Vue3.0响应式框架在设计上,将视图渲染和数据响应式完全分离开来。将响应式核心方法effect从原有的Watcher中抽离。这样,当我们只需要监听数据响应某种逻辑回调(例如监听某个text属性的变化…...
HTML 中的常用标签用法
HTML是构建Web页面的基础语言,其中包含许多不同类型的标签。这些标签由尖括号包围,以指示浏览器如何呈现文本。下面是HTML中的一些常用标签以及它们的使用方法: 标题标签(h1-h6) 标题标签用于标识页面内容的标题&…...
React 第五十五节 Router 中 useAsyncError的使用详解
前言 useAsyncError 是 React Router v6.4 引入的一个钩子,用于处理异步操作(如数据加载)中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误:捕获在 loader 或 action 中发生的异步错误替…...
家政维修平台实战20:权限设计
目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系,主要是分成几个表,用户表我们是记录用户的基础信息,包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题,不同的角色…...
linux 错误码总结
1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...
屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!
5月28日,中天合创屋面分布式光伏发电项目顺利并网发电,该项目位于内蒙古自治区鄂尔多斯市乌审旗,项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站,总装机容量为9.96MWp。 项目投运后,每年可节约标煤3670…...
Keil 中设置 STM32 Flash 和 RAM 地址详解
文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...
NLP学习路线图(二十三):长短期记忆网络(LSTM)
在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...
使用 SymPy 进行向量和矩阵的高级操作
在科学计算和工程领域,向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能,能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作,并通过具体…...
怎么让Comfyui导出的图像不包含工作流信息,
为了数据安全,让Comfyui导出的图像不包含工作流信息,导出的图像就不会拖到comfyui中加载出来工作流。 ComfyUI的目录下node.py 直接移除 pnginfo(推荐) 在 save_images 方法中,删除或注释掉所有与 metadata …...
tomcat入门
1 tomcat 是什么 apache开发的web服务器可以为java web程序提供运行环境tomcat是一款高效,稳定,易于使用的web服务器tomcathttp服务器Servlet服务器 2 tomcat 目录介绍 -bin #存放tomcat的脚本 -conf #存放tomcat的配置文件 ---catalina.policy #to…...
android RelativeLayout布局
<?xml version"1.0" encoding"utf-8"?> <RelativeLayout xmlns:android"http://schemas.android.com/apk/res/android"android:layout_width"match_parent"android:layout_height"match_parent"android:gravity&…...
