目录
- 专栏导读
- 一、题目描述
- 二、输入描述
- 三、输出描述
- 四、解题思路
- 五、Java算法源码
- 六、效果展示
- 1、输入
- 2、输出
- 3、说明
- 4、再输入
- 5、再输出
- 6、说明
华为OD机试 2023B卷题库疯狂收录中,刷题点这里
专栏导读
本专栏收录于《华为OD机试(JAVA)真题(A卷+B卷)》。
刷的越多,抽中的概率越大,每一题都有详细的答题思路、详细的代码注释、样例测试,发现新题目,随时更新,全天CSDN在线答疑。
一、题目描述
一个文件目录的数据格式为:
目录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,以逗号分隔
三、输出描述
待查询目录及其子目录的大小之和。
四、解题思路
题意描述的很复杂,其实很简单。
- 第一行输入目录的个数 + 待查询的目录id;
- 接下来的M行,输入目录id 本目录中文件大小(子目录id列表),比如1 20 (2),表示目录1的文件大小为20,包含子目录2;
- 最后要求输出目录+子目录的文件大小之和。
比如输入:
3 1
1 10 (2)
2 20 (3)
3 30 (4)
- 目录的个数为3,从1开始;
- 1的大小为10,子目录2;
- 2的大小为20,子目录3,;
- 3的大小为30,子目录4,没有;
- 输出10 + 20 +30 = 60;
如果输入改为:
3 2
1 10 (2)
2 20 (3)
3 30 (4)
- 目录的个数为3,从2开始;
- 2的大小为20,子目录3;
- 3的大小为30,子目录4,没有;
- 输出20 +30 = 50;
五、Java算法源码
package com.guor.od;
import java.util.Scanner;
import java.util.*;
import java.util.HashMap;
import java.util.stream.Collectors;
public class OdTest {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int[] line1 = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
// 目录的个数
int M = line1[0];
// 待查询的目录id
int N = line1[1];
/**
* 目录id包含的子目录id
*
* key:目录id
* value:子目录id
*/
Map<Integer, List<Integer>> idMap = new HashMap<>();
/**
* 目录大小信息
*
* key:目录id
* value:目录大小
*/
Map<Integer, Integer> dirMap = new HashMap<>();
for (int i = 0; i < M; i++) {
String[] lineM = sc.nextLine().split(" ");
// 目录id
int id = Integer.parseInt(lineM[0]);
// 本目录中文件大小
int size = Integer.parseInt(lineM[1]);
if(dirMap.containsKey(id)){
System.out.println("输入目录id不可重复,重复id:"+id);
return;
}
idMap.put(id, new ArrayList<>());
dirMap.put(id, size);
// 子目录id
String childs = lineM[2];
// 子目录是()时,长度为2,子目录为空1
if (childs.length() == 2) {
continue;
}
// 子目录数组
String[] childArr = childs.replace("(", "").replace(")", "").split(",");
List<Integer> childList = Arrays.stream(childArr).map(Integer::parseInt).collect(Collectors.toList());
idMap.get(id).addAll(childList);
}
// 递归获取有效的id集合
getIdList(N,idMap);
System.out.println("有效的id集合:"+idList);
int sum = 0;
// 获取有效的id的目录文件大小
for(Integer id : idList){
sum += dirMap.get(id);
}
// 输出目录大小之和
System.out.println(sum);
}
/**
* 递归获取有效的id集合
*
* @param start 待查询的目录id
* @param map id集合
* @return
*/
// 有效的id集合
static List<Integer> idList = new ArrayList<>();
private static void getIdList(int target, Map<Integer, List<Integer>> map) {
// 如果有子目录
if(map.containsKey(target)){
idList.add(target);
// 获取子集合id
List<Integer> list = map.get(target);
// 取过了,删除该id
map.remove(target);
// 递归子目录id,将其加入有效的id集合
for(Integer id : list){
getIdList(id,map);
}
}else{// 如果没有子目录,直接将其加入idList
idList.add(target);
}
}
}
六、效果展示
1、输入
3 1
1 10 (2)
2 20 (3)
3 30 ()
2、输出
60
3、说明
- 一共3个目录id;
- 开始目录id为1,其大小为10,子目录id为2;
- 2的大小为20,子目录id为3;
- 3的大小为30,没有子目录;
- 故输出10 + 20 + 30 = 60
4、再输入
5 1
1 10 (2,3,5)
2 20 ()
3 30 ()
4 40 (1)
5 50 (2)
5、再输出
130
6、说明
- 一共5个目录id;
- 开始目录id为1,其大小为10,子目录id为2,3,5;
- 2的大小为20,没有子目录;
- 3的大小为30,没有子目录;
- 5的大小为50,子目录为2;
- 2的大小为20,没有子目录;
- 故输出10 + 20 + 30 + 50 + 20 = 130
思路如此清晰,来,打开idea,试一下~~
🏆下一篇:华为OD机试真题 Java 实现【路灯照明问题】【2022Q4 100分】,感谢fly晨发现这个问题,并提供更优质的算法
🏆本文收录于,华为OD机试(JAVA)真题(A卷+B卷)
刷的越多,抽中的概率越大,每一题都有详细的答题思路、详细的代码注释、样例测试,发现新题目,随时更新,全天CSDN在线答疑。