文件目录大小

一、题目描述

一个文件目录的数据格式为: 目录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列表（以逗号分隔）。

输出描述

• 待查询目录及其子目录的大小之和

三、示例

四、解题思路

1. 核心思想

树形结构存储 + 深度优先搜索（DFS）递归累加：先用哈希表存储所有目录的结构，再通过递归遍历目标目录的所有子目录，把自身大小和所有子目录大小相加，得到总大小。

2. 问题本质分析

这是一个树形结构递归求和问题：

• 数据结构：目录树（一个目录可以包含多个子目录，是典型的树形结构）
• 要求：计算指定根目录 + 所有下级子目录的大小总和
• 本质：树的遍历 + 节点值累加。

3. 核心逻辑

1. 解析输入，把每个目录的id、大小、子目录存储到Map中；
2. 从目标目录开始递归：
   • 先加上当前目录自身大小
   • 再递归计算每一个子目录的总大小
   • 所有子目录结果累加
3. 递归结束后返回完整总和。

4. 步骤拆解

1. 输入读取与解析

   • 读取目录数量 M 和目标目录 ID
   • 逐行解析目录信息，拆分出 id、自身大小、子目录列表

2. 结构存储

   • 使用Map<Integer, Dir>存储所有目录
   • 方便通过目录 id 快速找到对应目录信息

3. 递归 DFS 计算总大小

   • 获取当前目录大小
   • 遍历所有子目录，递归计算子目录总大小
   • 累加所有值得到当前目录的总大小

4. 输出结果

   • 打印目标目录的最终总大小

五、代码实现

import java.util.*; public class Main { // 目录结构：key=目录id，value=[本目录大小, 子目录id列表] static Map<Integer, Dir> map = new HashMap<>(); static class Dir { int size; List<Integer> children; public Dir(int size, List<Integer> 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]); // 解析子目录 List<Integer> 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; } }