专栏导读
本专栏收录于《华为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在线答疑。