宁波百度网站建设,百度浏览器下载安装,长沙网站制作品牌,网页平面设计培训学校题目 一个文件目录的数据格式为:目录id,本目录中文件大小#xff0c;(子目录id列表)。其中目录id全局唯一#xff0c; 取值范围[1 ,200]#xff0c;本目录中文件大小范围[1,1000]#xff0c;子目录id列表个数[0,10] 例如: 1 20 (2,3)表示目录1中文件总大小是20,有两个子目录…题目 一个文件目录的数据格式为:目录id,本目录中文件大小(子目录id列表)。其中目录id全局唯一 取值范围[1 ,200]本目录中文件大小范围[1,1000]子目录id列表个数[0,10] 例如: 1 20 (2,3)表示目录1中文件总大小是20,有两个子目录id分别是2和3 现在输入一个文件系统中所有目录信息以及待查询的目录id,返回这个目录和及该目录所有子目录的大小之和 输入描述 第一行为两个数字MN,分别表示目录的个数和待查询的目录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 101545 示例2: 输入 4 2 4 20 () 5 30 () 2 10 (4,5) 1 40() 输出 60 说明 目录2包含2个子目录4和5总的大小为102030 60 思路 使用两个map分别【存储id-本目录大小】【id-子目录列表】假设分别定义为MapInteger, Integer sizeMap MapInteger, int[] subDirMap 方案一dfs遍历即可设计函数dfs(n),n代表待查询目录id 记录当前目录大小:ressizeMap.get(n) 定义dfs的终止条件如果子目录为空终止递归直接返回res 否则遍历子目录list使用res累加上dfs(s)s代表每次遍历的子目录id 最后返回res即可 方案二利用对列实现 初始对列deque加入待查询目录iddeque.add(n); 遍历deque如果deque不为空那么弹出对列得到目录ididdeque.pollFirst(); 根据id在sizeMap 中找到当前目录的大小ressizeMap.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 MapInteger, Integer sizeMap new HashMap();private static MapInteger, 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) {LinkedListInteger deque new LinkedList();deque.add(n);int res 0;while (!deque.isEmpty()) {int id deque.pollFirst();if(id0) 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查看当前专栏更新的所有题目。
