【华为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），查看当前专栏更新的所有题目。