文件目录大小

一、题目描述一个文件目录的数据格式为: 目录id本目录中文件大小(子目录id列表)其中目录id全局唯一取值范围[1,200]本目录中文件大小范围[1,1000]子目录id列表个数[0,10]。例如 : 1 20 (2,3)表示目录1中文件总大小是20有两人子目录id分别是2和3。现在输入一个文件系统中所有日录信息以及待查询的目录id返回这个目录和及该目录所有子目录的大小之和。二、输入输出描述输入描述第一行两个数字MN分别表示目录的个数和待查询的目录id.1≤M≤1001≤N≤200接下来M行每行为1个目录的数据格式目录id 本目录中文件大小 子目录id列表以逗号分隔。输出描述待查询目录及其子目录的大小之和三、示例输入3 13 15 (0)1 20 (2)2 10 (3)输出45说明目录1大小为20包含一个子目录2(大小为10)子目录2包含人子目录3(大小为15)总的大小为20101545输入4 24 20 ()5 30 ()2 10 (4,5)1 40 ()输出60说明目录2包含2个子目录4和5总的大小为102030 60四、解题思路1. 核心思想树形结构存储 深度优先搜索DFS递归累加先用哈希表存储所有目录的结构再通过递归遍历目标目录的所有子目录把自身大小和所有子目录大小相加得到总大小。2. 问题本质分析这是一个树形结构递归求和问题数据结构目录树一个目录可以包含多个子目录是典型的树形结构要求计算指定根目录 所有下级子目录的大小总和本质树的遍历 节点值累加。3. 核心逻辑解析输入把每个目录的id、大小、子目录存储到Map中从目标目录开始递归先加上当前目录自身大小再递归计算每一个子目录的总大小所有子目录结果累加递归结束后返回完整总和。4. 步骤拆解输入读取与解析读取目录数量 M 和目标目录 ID逐行解析目录信息拆分出 id、自身大小、子目录列表结构存储使用MapInteger, Dir存储所有目录方便通过目录 id 快速找到对应目录信息递归 DFS 计算总大小获取当前目录大小遍历所有子目录递归计算子目录总大小累加所有值得到当前目录的总大小输出结果打印目标目录的最终总大小五、代码实现import java.util.*; public class Main { // 目录结构key目录idvalue[本目录大小, 子目录id列表] static MapInteger, Dir map new HashMap(); static class Dir { int size; ListInteger children; public Dir(int size, ListInteger children) { this.size size; this.children children; } } public static void main(String[] args) { Scanner sc new Scanner(System.in); int M sc.nextInt(); int target sc.nextInt(); sc.nextLine(); // 换行 for (int i 0; i M; i) { String line sc.nextLine().trim(); // 拆分 id 和大小部分 String[] left line.split(\\()[0].trim().split(\\s); int id Integer.parseInt(left[0]); int size Integer.parseInt(left[1]); // 解析子目录 ListInteger children new ArrayList(); String childStr line.split(\\()[1].split(\\))[0].trim(); if (!childStr.isEmpty() !childStr.equals(0)) { String[] cs childStr.split(,); for (String c : cs) { children.add(Integer.parseInt(c.trim())); } } map.put(id, new Dir(size, children)); } // 递归计算总和 System.out.println(dfs(target)); } // 递归求当前目录 所有子目录总和 static int dfs(int id) { Dir dir map.get(id); int total dir.size; for (int child : dir.children) { total dfs(child); } return total; } }