【华为OD题库-023】文件目录大小-java
题目
一个文件目录的数据格式为:目录id,本目录中文件大小,(子目录id列表)。其中目录id全局唯一, 取值范围[1 ,200],本目录中文件大小范围[1,1000],子目录id列表个数[0,10]
例如: 1 20 (2,3)表示目录1中文件总大小是20,有两个子目录,id分别是2和3
现在输入一个文件系统中所有目录信息,以及待查询的目录id,返回这个目录和及该目录所有子目录的大小之和
输入描述
第一行为两个数字M,N,分别表示目录的个数和待查询的目录id.
1≤M≤100
1≤N≤200
接下来M行,每行为1个目录的数据
目录id 本目录中文件大小(子目录id列表)
子目录列表中的子目录id以逗号分隔
输出描述
待查询目录及其子目录的大小之和
示例1:
输入
3 1
3 15 (0)
1 20 (2)
2 10 (3)
输出
45
说明
目录1大小为20,包含一个子目录2(大小为10),子目录2包含一个子目录3(大小为15),总的大小为20+ 10+15=45
示例2:
输入
4 2
4 20 ()
5 30 ()
2 10 (4,5)
1 40()
输出
60
说明
目录2包含2个子目录4和5,总的大小为10+20+30= 60
思路
使用两个map分别【存储id-本目录大小】,【id-子目录列表】,假设分别定义为:Map<Integer, Integer> sizeMap ,Map<Integer, int[]> subDirMap
方案一:dfs遍历即可,设计函数dfs(n),n代表待查询目录id记录当前目录大小:res=sizeMap.get(n)
定义dfs的终止条件:如果子目录为空,终止递归,直接返回res
否则,遍历子目录list,使用res累加上dfs(s),s代表每次遍历的子目录id
最后返回res即可方案二:利用对列实现
初始对列deque加入待查询目录id:deque.add(n);
遍历deque,如果deque不为空,那么弹出对列,得到目录id:id=deque.pollFirst();
根据id在sizeMap 中找到当前目录的大小,res+=sizeMap.get(id);
根据id在subDirMap中找到当前目录的子目录列表,将子目录列表加入到deque中
遍历完成后,将res返回即可
题解
package hwod;import java.util.*;
import java.util.stream.Collectors;public class DirectorySize {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int m = sc.nextInt();int n = sc.nextInt();sc.nextLine();String[] directoryInfos = new String[m];for (int i = 0; i < m; i++) {directoryInfos[i] = sc.nextLine();}System.out.println(getDirectorySize(directoryInfos, n));}private static Map<Integer, Integer> sizeMap = new HashMap<>();private static Map<Integer, int[]> subDirMap = new HashMap<>();private static int getDirectorySize(String[] infos, int n) {for (int i = 0; i < infos.length; i++) {String[] lines = infos[i].split(" ");int id = Integer.parseInt(lines[0]);int size = Integer.parseInt(lines[1]);sizeMap.put(id, size);String subDirsStr = lines[2].substring(1, lines[2].length() - 1);if ("".equals(subDirsStr)) {subDirMap.put(id, new int[0]);} else {subDirMap.put(id, Arrays.stream(subDirsStr.split(",")).mapToInt(Integer::parseInt).toArray());}}if (!sizeMap.containsKey(n)) return -1;// return dfs(n);return getForQueue(n);}//方案一:private static int dfs(int n) {int[] subdirs = subDirMap.get(n);int res = sizeMap.get(n);if (subdirs.length == 0) return res;for (int i = 0; i < subdirs.length; i++) {if(!sizeMap.containsKey(subdirs[i])) continue; //兼容错误数据,如:(0,2),(-1,2,999)res += dfs(subdirs[i]);}return res;}//方案二:对列实现private static int getForQueue(int n) {LinkedList<Integer> deque = new LinkedList<>();deque.add(n);int res = 0;while (!deque.isEmpty()) {int id = deque.pollFirst();if(id==0) continue; //如果修改为break,那么子目录不允许这种情况(0,2),(-1,2,999)存在res += sizeMap.get(id);deque.addAll(Arrays.stream(subDirMap.get(id)).boxed().collect(Collectors.toList()));}return res;}}
推荐
如果你对本系列的其他题目感兴趣,可以参考华为OD机试真题及题解(JAVA),查看当前专栏更新的所有题目。
相关文章:
【华为OD题库-023】文件目录大小-java
题目 一个文件目录的数据格式为:目录id,本目录中文件大小,(子目录id列表)。其中目录id全局唯一, 取值范围[1 ,200],本目录中文件大小范围[1,1000],子目录id列表个数[0,10] 例如: 1 20 (2,3)表示目录1中文件总大小是20,有两个子目录…...
4. 【自动驾驶与机器人中的SLAM技术】点云中的拟合问题和K近邻
目录 1.在三维体素中定义 NEARBY14,实现 14 格最近邻的查找。2.推导arg max||Ad||22的解为ATA的最大特征向量或者奇异向量。3. 将本节的最近邻算法与一些常见的近似最近邻算法进行对比,比如nanoflann,给出精度指标和时间效率指标。4. 也欢迎大…...
正点原子嵌入式linux驱动开发——Linux ADC驱动
在之前的笔记中,学习了如何给ICM20608编写IIO驱动,ICM20608本质就是ADC,因此纯粹的ADC驱动也是IIO驱动框架的。本章就学习一下如何使用STM32MP1内部的ADC,并且在学习巩固一下IIO驱动。 ADC简介 ADC ADC,Analog to D…...
自动化测试介绍和分类,看这一篇就够了
📢专注于分享软件测试干货内容,欢迎点赞 👍 收藏 ⭐留言 📝 如有错误敬请指正!📢交流讨论:欢迎加入我们一起学习!📢资源分享:耗时200小时精选的「软件测试」资…...
Debian中执行脚本 提示没有那个文件或目录
原因是在脚本头有句: ~/.bash_profile这个在CentOS里执行是正常的,但在Debian中是没有的,它改成了: ~/.profile一、区别: 1、/etc/profile: 此文件为系统的每个用户设置环境信息,当用户第一次登录时,该文…...
放松鸭-技术支持
“放松鸭”利用苹果手表的HRV心率变异性和静息心率等数据进行分析,帮助您了解当前身体疲劳和心理压力程度,并及时提醒您的压力状态。我们的目标是让您更好地感知、管理和应对压力,让您的身心得到平静和放松。通过读取您的心脏数据,…...
Vue 报错error:0308010C:digital envelope routines::unsupported
你遇到的错误,error:0308010C:digital envelope routines::unsupported,与 OpenSSL 相关,表明在你的 Vue.js 应用中可能存在与加密操作相关的问题。这种错误通常出现在 OpenSSL 库存在不匹配或问题的情况下。 以下是解决此问题的一些建议&am…...
Android 9.0 隐藏设置中一级菜单“已连接的设备”
Android 9.0 隐藏设置中一级菜单“已连接的设备” 接到客户反馈需要隐藏设备设置中的“已连接的设备”一级菜单,具体修改参照如下: /vendor/mediatek/proprietary/packages/apps/MtkSettings/src/com/android/settings/SettingsActivity.java somethin…...
Hive开窗函数根据特定条件取上一条最接近时间的数据(根据条件取窗口函数的值)
一、Hive开窗函数根据特定条件取上一条最接近时间的数据(单个开窗函数,实际取两个窗口) 针对于就诊业务,一次就诊,多个处方,处方结算时间可能不一致,然后会有多个AI助手推荐用药,会…...
指针与函数
指针函数:函数的返回值可以是整型值、浮点型值、字符型值等,在C语言中还允许一个函数的返回值是一个指针(地址),这种返回指针的函数称为指针函数。 指针函数语法格式: 基类型 * 函数名(参数列…...
GBase8a-GDCA-第二次阶段测试
文章目录 主要内容在这里插入图片描述 在这里插入图片描述 总结 主要内容 GBase8a-GDCA-第二次阶段测试及答案 总结 以上是今天要讲的内容,GBase8a-GDCA-第二次阶段测试…...
Go 理解零值
在 Go 语言中,零值(Zero Value)是指在声明变量但没有显式赋值的情况下,变量会被自动赋予一个默认值。这个默认值取决于变量的类型,不同类型的变量会有不同的零值。零值是 Go 语言中的一个重要概念,因为它确…...
SQL编写规范【干货】
编写本文档的目的是保证在开发过程中产出高效、格式统一、易阅读、易维护的SQL代码。 1 编写目 2 SQL书写规范 3 SQL编写原则 获取所有软件开发资料:点我获取...
2.5 Windows驱动开发:DRIVER_OBJECT对象结构
在Windows内核中,每个设备驱动程序都需要一个DRIVER_OBJECT对象,该对象由系统创建并传递给驱动程序的DriverEntry函数。驱动程序使用此对象来注册与设备对象和其他系统对象的交互,并在操作系统需要与驱动程序进行交互时使用此对象。DRIVER_OB…...
[ubuntu]ubuntu上安装jdk1.8教程
首先需要去官方网站去下载对应jdk1.8版本: https://www.oracle.com/java/technologies/downloads/ 您也可以去csdn搜索我提供jdk安装包 这里以jdk-8u201-linux-x64.tar.gz为例子,首先下载安装后解压 tar -zxvf jdk-8u201-linux-x64.tar.gz 比如我解…...
金蝶云星空其他出库单保存提示序列号不一致
文章目录 金蝶云星空其他出库单保存提示序列号不一致保存报错初步分析总结 金蝶云星空其他出库单保存提示序列号不一致 保存报错 显示单据数量0.序列号数量3 初步分析 输入实发数量没有触发序列号数量的计算 检查实发数量的值更新事件 实发数量和序列号数量的转换ÿ…...
FBI:皇家勒索软件要求350名受害者支付2.75亿美元
导语 最近,FBI和CISA联合发布的一份通告中透露,自2022年9月以来,皇家勒索软件(Royal ransomware)已经入侵了全球至少350家组织的网络。这次更新的通告还指出,这个勒索软件团伙的赎金要求已经超过了2.75亿美…...
Layout工程师们--Allegro X AI实现pcb自动布局布线
Cadence 推出 Allegro X AI,旨在加速 PCB 设计流程,可将周转时间缩短 10 倍以上 楷登电子(美国 Cadence 公司,NASDAQ:CDNS)今日宣布推出 Cadence Allegro X AI technology,这是 Cadence 新一代…...
Hive入门--学习笔记
1,Apache Hive概述 定义: Hive是由Facebook开源用于解决海量结构化日志的数据统计,它是基于大数据生态圈Hadoop的一个数据仓库工具。 作用: Hive可以用于将结构化的数据文件【映射】为一张表,并提供类SQL查询功能。 H…...
【nlp】1文本预处理总括目录(附各章节链接)
文本预处理 1. 文本预处理机器作用2. 文本预处理包含的主要环节2.1 文本处理的基本方法2.1.1 分词2.1.2 词性标注2.2.3 命名实体标注2.2 文本张量表示方法2.2.1 one-hot编码2.2.2 Word2vec2.2.3 Word Embedding2.3 文本语料的数据分析2.3.1 标签数量分布2.3.2 句子长度分布2.3.…...
Docker 离线安装指南
参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性,不同版本的Docker对内核版本有不同要求。例如,Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本,Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...
云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地
借阿里云中企出海大会的东风,以**「云启出海,智联未来|打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办,现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...
【磁盘】每天掌握一个Linux命令 - iostat
目录 【磁盘】每天掌握一个Linux命令 - iostat工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景 注意事项 【磁盘】每天掌握一个Linux命令 - iostat 工具概述 iostat(I/O Statistics)是Linux系统下用于监视系统输入输出设备和CPU使…...
现代密码学 | 椭圆曲线密码学—附py代码
Elliptic Curve Cryptography 椭圆曲线密码学(ECC)是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础,例如椭圆曲线数字签…...
css的定位(position)详解:相对定位 绝对定位 固定定位
在 CSS 中,元素的定位通过 position 属性控制,共有 5 种定位模式:static(静态定位)、relative(相对定位)、absolute(绝对定位)、fixed(固定定位)和…...
DBAPI如何优雅的获取单条数据
API如何优雅的获取单条数据 案例一 对于查询类API,查询的是单条数据,比如根据主键ID查询用户信息,sql如下: select id, name, age from user where id #{id}API默认返回的数据格式是多条的,如下: {&qu…...
Matlab | matlab常用命令总结
常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...
图表类系列各种样式PPT模版分享
图标图表系列PPT模版,柱状图PPT模版,线状图PPT模版,折线图PPT模版,饼状图PPT模版,雷达图PPT模版,树状图PPT模版 图表类系列各种样式PPT模版分享:图表系列PPT模板https://pan.quark.cn/s/20d40aa…...
如何在网页里填写 PDF 表格?
有时候,你可能希望用户能在你的网站上填写 PDF 表单。然而,这件事并不简单,因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件,但原生并不支持编辑或填写它们。更糟的是,如果你想收集表单数据ÿ…...
Linux 中如何提取压缩文件 ?
Linux 是一种流行的开源操作系统,它提供了许多工具来管理、压缩和解压缩文件。压缩文件有助于节省存储空间,使数据传输更快。本指南将向您展示如何在 Linux 中提取不同类型的压缩文件。 1. Unpacking ZIP Files ZIP 文件是非常常见的,要在 …...
