2025 B卷 100分 题型
本专栏内全部题目均提供Java、python、JavaScript、C、C++、GO六种语言的最佳实现方式；
并且每种语言均涵盖详细的问题分析、解题思路、代码实现、代码详解、3个测试用例以及综合分析；
本文收录于专栏：《2025华为OD真题目录+全流程解析+备考攻略+经验分享》
华为OD机试真题《文件目录大小》：
文章快捷目录
题目描述及说明
Java
python
JavaScript
C++
C
GO
题目名称：文件目录大小
知识点：字符串、栈操作（DFS）、逻辑处理
时间限制：1秒
空间限制：256MB
限定语言：不限
题目描述
一个文件目录的数据格式为：目录id，本目录中文件大小，(子目录id列表)。其中：
目录id全局唯一，取值范围为[1, 200]
本目录文件大小范围为[1, 1000]
子目录id列表个数为[0, 10]
输入描述
第一行：两个整数 M 和 N，表示目录个数和待查询的目录id（1 ≤ M ≤ 100，1 ≤ N ≤ 200）。
后续 M 行：每行描述一个目录，格式为 目录id 文件大小 (子目录列表)，例如 1 20 (2,3)。
输出描述
待查询目录及其所有子目录的文件大小之和。
示例
输入1
3 1
3 15 ()
1 20 (2)
2 10 (3)
输出1
45
输入2
4 2
4 20 ()
5 30 ()
2 10 (4,5)
1 40 ()
输出2
60
题目描述
Java
问题分析
这道题目要求计算指定目录及其所有子目录的文件大小总和。我们可以将其视为一个树形结构问题，每个目录作为节点，子目录作为子节点。以下是详细的解决思路和代码实现。
解决思路
输入解析：首先读取目录数目M和目标目录N，然后逐行解析每个目录的信息，包括目录ID、文件大小和子目录列表。
数据结构：使用两个哈希表分别存储目录的大小和子目录列表，便于快速查找。
递归计算：从目标目录开始，递归遍历所有子目录，累加文件大小总和。
代码实现
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 读取目录个数M和待查询的目录id N
int M = scanner.nextInt();
int N = scanner.nextInt();
scanner.nextLine(); // 跳过剩余换行符
// 使用哈希表存储目录的大小和子目录列表
Map<Integer, Integer> sizeMap = new HashMap<>();
Map<Integer, List<Integer>> childrenMap = new HashMap<>();
for (int i = 0; i < M; i++) {
String line = scanner.nextLine().trim();
// 使用正则表达式按一个或多个空格分割行数据
String[] parts = line.split("\s+");
int dirId = Integer.parseInt(parts[0]);
int size = Integer.parseInt(parts[1]);
String childrenStr = parts[2]; // 子目录列表部分，如"(2,3)"
// 处理子目录字符串，提取子目录id
childrenStr = childrenStr
.substring(1, childrenStr.length() - 1) // 去掉括号
.trim(); // 去除可能存在的首尾空格
List<Integer> children = new ArrayList<>();
if (!childrenStr.isEmpty()) {
// 处理非空子目录列表
String[] childIds = childrenStr.split(",");
for (String childId : childIds) {
childId = childId.trim(); // 去除每个子目录id的前后空格
if (!childId.isEmpty()) {
children.add(Integer.parseInt(childId));
}
}
}
// 将解析后的数据存入哈希表
sizeMap.put(dirId, size);
childrenMap.put(dirId, children);
}
// 计算目标目录及其所有子目录的总大小
int totalSize = calculateTotalSize(N, sizeMap, childrenMap);
System.out.println(totalSize);
}
// 递归计算目录总大小
private static int calculateTotalSize(int dirId, Map<Integer, Integer> sizeMap, Map<Integer, List<Integer>> childrenMap) {
// 获取当前目录的大小
int sum = sizeMap.get(dirId);
// 遍历所有子目录，递归累加
for (int childId : childrenMap.get(dirId)) {
sum += calculateTotalSize(childId, sizeMap, childrenMap);
}
return sum;
}
}
代码解析
输入处理：
使用Scanner读取输入，第一行读取M和N。
scanner.nextLine()用于跳过换行符，确保后续读取正确。
数据结构初始化：
sizeMap存储目录ID到文件大小的映射。
childrenMap存储目录ID到子目录列表的映射。
解析目录信息：
每行按空格分割为三部分：目录ID、文件大小、子目录列表字符串。
处理子目录字符串：去除括号和空格，分割后转为整数列表。
递归计算总大小：
递归函数calculateTotalSize从目标目录开始，累加当前目录大小及其所有子目录的总大小。
综合分析
高效的数据结构：哈希表提供O(1)时间复杂度的查找，适合快速访问目录信息。
递归的简洁性：递归自然契合树形结构，代码简洁易懂，适合处理嵌套子目录。
健壮性：正确处理输入中的各种格式（如空格、空子目录列表），确保解析准确。
时间复杂度：每个目录仅访问一次，总时间复杂度为O(M)，满足题目限制。
通过这种方法，能清晰理解目录结构的遍历和递归计算过程，确保正确高效地解决问题。
python
题目分析
题目要求计算指定目录及其所有子目录的文件大小总和。每个目录信息以 目录id 文件大小 (子目录列表) 的格式给出，我们需要从输入中解析这些信息，并递归地累加目标目录及其所有子目录的文件大小。
解决思路
输入解析：读取目录数量 M 和目标目录 N，解析每个目录的信息。
数据结构：用字典存储目录的文件大小和子目录列表。
递归计算：从目标目录开始，递归遍历所有子目录，累加文件大小总和。
代码实现
def main():
import sys
# 读取输入
lines = [line.strip() for line in sys.stdin if line.strip()]
# 解析 M 和 N
M, N = map(int, lines[0].split())
# 初始化存储结构
size_map = {
} # key: 目录id, value: 文件大小
children_map = {
} # key: 目录id, value: 子目录列表
# 处理后续 M 行数据
for line in lines[1:M+1]: # 前 M 行是目录信息
parts = line.split()
dir_id = int(parts[0])
file_size = int(parts[1])
children_str = parts[2] # 子目录部分，例如 "(2,3)"
# 处理子目录字符串
children_str = children_str[1:-1].strip() # 去掉括号和首尾空格
children = []
if children_str: # 如果有子目录
# 分割并转换为整数列表
children = list(map(int, [c.strip() for c in children_str.split(',') if c.strip()]))
# 存储到字典
size_map[dir_id] = file_size
children_map[dir_id] = children
# 递归计算总大小
def calculate_total_size(dir_id):
total = size_map[dir_id] # 当前目录的大小
for child in children_map[dir_id]: # 遍历所有子目录
total += calculate_total_size(child)
return total
# 输出结果
print(calculate_total_size(N))
if __name__ == "__main__":
main()
代码解析
输入处理：
lines = [line.strip() ...]：读取所有输入行并去除首尾空格。
M, N = map(int, lines[0].split())：解析第一行的 M 和 N。
数据结构初始化：
size_map 和 children_map 是字典，用于快速查询目录的文件大小和子目录列表。
解析目录信息：
parts = line.split()：将每行按空格分割成三部分。
dir_id = int(parts[0]) 和 file_size = int(parts[1])：解析目录 ID 和文件大小。
children_str = parts[2][1:-1].strip()：提取子目录字符串并去掉括号。
children = list(map(int, ...))：将子目录字符串分割成整数列表（例如 "2,3" → [2,3]）。
递归计算总大小：
calculate_total_size 函数递归遍历子目录，累加文件大小。
total = size_map[dir_id]：当前目录的大小。
for child in children_map[dir_id]：遍历所有子目录，递归计算它们的总大小。
综合分析
高效的数据结构：Python 的字典（dict）提供 O(1) 的查询速度，适合快速访问目录信息。
递归的简洁性：递归天然适合树形结构，代码直观且易于理解。
健壮的输入处理：
使用 strip() 和 split() 处理可能的空格干扰。
空子目录列表（如 "()"）会被正确解析为空列表。
时间复杂度：每个目录仅访问一次，时间复杂度为 O(M)，完全满足题目约束（1 ≤ M ≤ 100）。
示例测试
输入1：
3 1
3 15 ()
1 20 (2)
2 10 (3)
解析：
目录1的大小是20，子目录是2。
目录2的大小是10，子目录是3。
目录3的大小是15，无子目录。
计算过程：
calculate_total_size(1) → 20 + calculate_total_size(2)
calculate_total_size(2) → 10 + calculate_total_size(3)
calculate_total_size(3) → 15
总和：20 + 10 + 15 = 45。
输入2：
4 2
4 20 ()
5 30 ()
2 10 (4,5)
1 40 ()
解析：
目录2的大小是10，子目录是4和5。
目录4和5的大小分别是20和30，无子目录。
计算过程：
calculate_total_size(2) → 10 + calculate_total_size(4) + calculate_total_size(5)
calculate_total_size(4) → 20
calculate_total_size(5) → 30
总和：10 + 20 + 30 = 60。
总结
通过递归遍历目录树，结合 Python 的高效字典和简洁语法，代码既清晰又高效。这种方法在保证正确性的同时，完美适配题目中的数据规模，是最优的实现方案。
JavaScript
题目分析
题目要求计算指定目录及其所有子目录的文件大小总和。每个目录信息以 目录id 文件大小 (子目录列表) 的格式给出，我们需要从输入中解析这些信息，并递归地累加目标目录及其所有子目录的文件大小。
解决思路
输入解析：读取目录数量 M 和目标目录 N，解析每个目录的信息。
数据结构：用对象存储目录的文件大小和子目录列表。
递归计算：从目标目录开始，递归遍历所有子目录，累加文件大小总和。
代码实现
const fs = require('fs');
function main() {
// 读取所有输入行并去除首尾空格
const lines = fs.readFileSync(0).toString().trim().split('
');
// 解析 M 和 N
const firstLine = lines[0].trim().split(/s+/);
const M = parseInt(firstLine[0], 10);
const N = parseInt(firstLine[1], 10);
// 初始化存储结构
const sizeMap = {
}; // key: 目录id, value: 文件大小
const childrenMap = {
}; // key: 目录id, value: 子目录列表
// 处理后续 M 行数据
for (let i = 1; i <= M; i++) {
const line = lines[i].trim();
// 使用正则表达式匹配目录信息格式
const match = line.match(/^(d+)s+(d+)s+((.*))$/);
if (!match) {
continue; // 输入格式错误时跳过（根据题目描述，输入是合法的）
}
const dirId = parseInt(match[1], 10);
const fileSize = parseInt(match[2], 10);
const childrenStr = match[3].trim(); // 提取子目录字符串
// 处理子目录字符串
let children = [];
if (childrenStr) {
children = childrenStr.split(',') // 按逗号分割
.map(c => c.trim()) // 去除每个子目录id的前后空格
.filter(c => c !== '') // 过滤空字符串
.map(c => parseInt(c, 10)); // 转换为数字
}
// 存储到对象中
sizeMap[dirId] = fileSize;
childrenMap[dirId] = children;
}
// 递归计算总大小
function calculateTotalSize(dirId) {
let total = sizeMap[dirId]; // 当前目录的大小
for (const childId of childrenMap[dirId]) {
total += calculateTotalSize(childId); // 递归累加子目录大小
}
return total;
}
// 输出结果
console.log(calculateTotalSize(N));
}
main();
代码解析
输入处理：
fs.readFileSync(0) 读取标准输入，.split(' 分割成行数组。
')
lines[0].trim() 处理第一行，split(/s+/) 按空格分割得到 M 和 N。
数据结构初始化：
sizeMap 和 childrenMap 是普通对象，用于快速查询目录信息。
解析目录信息：
line.match(/^(d+)s+(d+)s+((.*))$/) 用正则表达式精准匹配目录格式。
childrenStr.split(',') 分割子目录字符串，map 和 filter 确保格式正确。
递归计算总大小：
calculateTotalSize 递归遍历子目录，累加文件大小。
for (const childId of childrenMap[dirId]) 遍历所有子目录。
综合分析
高效的正则匹配：用正则表达式精准提取目录信息，避免空格干扰。
递归的简洁性：天然适合树形结构，代码直观易懂。
健壮性：
trim() 和 split(',') 处理子目录中的空格。
空子目录列表（如 ()) 会被解析为空数组。
时间复杂度：每个目录仅访问一次，时间复杂度为 O(M)，完全满足题目规模。
示例测试
输入1：
3 1
3 15 ()
1 20 (2)
2 10 (3)
解析：
目录1的大小是20，子目录是2。
目录2的大小是10，子目录是3。
目录3的大小是15，无子目录。
计算过程：
calculateTotalSize(1) → 20 + calculateTotalSize(2)
calculateTotalSize(2) → 10 + calculateTotalSize(3)
calculateTotalSize(3) → 15
总和：20 + 10 + 15 = 45。
输入2：
4 2
4 20 ()
5 30 ()
2 10 (4,5)
1 40 ()
解析：
目录2的大小是10，子目录是4和5。
目录4和5的大小分别是20和30，无子目录。
计算过程：
calculateTotalSize(2) → 10 + calculateTotalSize(4) + calculateTotalSize(5)
calculateTotalSize(4) → 20
calculateTotalSize(5) → 30
总和：10 + 20 + 30 = 60。
总结
通过正则表达式精准解析输入，结合递归遍历目录树，JavaScript 代码在保证可读性的同时，高效解决问题。该方法完美适配题目要求，是理想的实现方案。
C++
题目分析
题目要求计算指定目录及其所有子目录的文件大小总和。每个目录信息以 目录id 文件大小 (子目录列表) 的格式给出，我们需要从输入中解析这些信息，并递归地累加目标目录及其所有子目录的文件大小。
解决思路
输入解析：读取目录数量 M 和目标目录 N，解析每个目录的信息。
数据结构：用 unordered_map 存储目录的文件大小和子目录列表。
递归计算：从目标目录开始，递归遍历所有子目录，累加文件大小总和。
代码实现
#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <sstream>
using namespace std;
// 辅助函数：去除字符串首尾的空格
string trim(const string& s) {
size_t start = s.find_first_not_of(" ");
if (start == string::npos) return "";
size_t end = s.find_last_not_of(" ");
return s.substr(start, end - start + 1);
}
// 辅助函数：按分隔符分割字符串
vector<string> split(const string& s, char delimiter) {
vector<string> tokens;
string token;
istringstream tokenStream(s);
while (getline(tokenStream, token, delimiter)) {
token = trim(token); // 去除每个分割部分的首尾空格
if (!token.empty()) {
tokens.push_back(token);
}
}
return tokens;
}
// 递归计算总大小
int calculateTotalSize(int dirId,
unordered_map<int, int>& sizeMap,
unordered_map<int, vector<int>>& childrenMap) {
int sum = sizeMap[dirId];
for (int childId : childrenMap[dirId]) {
sum += calculateTotalSize(childId, sizeMap, childrenMap);
}
return sum;
}
int main() {
int M, N;
cin >> M >> N;
cin.ignore(); // 忽略第一行后的换行符
// 存储目录信息：文件大小和子目录列表
unordered_map<int, int> sizeMap;
unordered_map<int, vector<int>> childrenMap;
for (int i = 0; i < M; ++i) {
string line;
getline(cin, line); // 读取整行输入
istringstream iss(line);
int dirId, fileSize;
string rest;
// 解析目录id和文件大小
iss >> dirId >> fileSize;
getline(iss, rest); // 读取剩余部分（子目录列表）
rest = trim(rest); // 去除首尾空格
// 处理子目录列表部分
if (rest.front() != '(' || rest.back() != ')') {
continue; // 输入格式错误（根据题目描述，输入是合法的）
}
string childrenStr = rest.substr(1, rest.size() - 2); // 去掉括号
childrenStr = trim(childrenStr); // 去除中间可能存在的空格
// 分割子目录字符串并转换为整数列表
vector<string> childTokens = split(childrenStr, ',');
vector<int> children;
for (const string& token : childTokens) {
if (!token.empty()) {
children.push_back(stoi(token));
}
}
// 存入哈希表
sizeMap[dirId] = fileSize;
childrenMap[dirId] = children;
}
// 计算并输出结果
cout << calculateTotalSize(N, sizeMap, childrenMap) << endl;
return 0;
}
代码解析
辅助函数：
trim：去除字符串首尾的空格。
split：按分隔符分割字符串，并清理每个部分的空格。
输入处理：
cin >> M >> N：读取目录数和目标目录。
cin.ignore()：清理输入缓冲区，防止后续 getline 读取错误。
解析目录信息：
getline(cin, line)：逐行读取目录信息。
iss >> dirId >> fileSize：提取目录 ID 和文件大小。
getline(iss, rest)：提取剩余部分的子目录列表字符串。
rest.substr(1, rest.size() - 2)：去掉括号，提取子目录内容。
递归计算：
calculateTotalSize：递归遍历子目录，累加文件大小总和。
综合分析
高效的数据结构：unordered_map 提供 O(1) 的查询效率。
健壮的输入处理：
使用 trim 和 split 处理输入中的空格。
支持子目录列表中的空格（如 "(2, 3)"）。
递归的简洁性：自然契合树形结构，代码直观易懂。
时间复杂度：每个目录仅访问一次，时间复杂度为 O(M)。
示例测试
输入1：
3 1
3 15 ()
1 20 (2)
2 10 (3)
解析：
目录1的大小是20，子目录是2。
目录2的大小是10，子目录是3。
目录3的大小是15，无子目录。
计算过程：
calculateTotalSize(1) → 20 + calculateTotalSize(2)
calculateTotalSize(2) → 10 + calculateTotalSize(3)
calculateTotalSize(3) → 15
总和：20 + 10 + 15 = 45。
输入2：
4 2
4 20 ()
5 30 ()
2 10 (4,5)
1 40 ()
解析：
目录2的大小是10，子目录是4和5。
目录4和5的大小分别是20和30，无子目录。
计算过程：
calculateTotalSize(2) → 10 + calculateTotalSize(4) + calculateTotalSize(5)
calculateTotalSize(4) → 20
calculateTotalSize(5) → 30
总和：10 + 20 + 30 = 60。
总结
通过 unordered_map 存储目录信息，结合递归遍历目录树，C++ 代码在保证性能的同时，完美适配题目要求。输入处理部分充分考虑了格式的灵活性，是高效且健壮的实现方案。
C
题目分析
题目要求计算指定目录及其所有子目录的文件大小总和。每个目录信息以 目录id 文件大小 (子目录列表) 的格式给出，我们需要解析输入并递归累加目标目录及其所有子目录的文件大小。
解决思路
输入解析：逐行读取目录信息，提取目录 ID、文件大小和子目录列表。
数据结构：使用结构体数组存储目录信息，利用目录 ID 直接索引。
递归计算：从目标目录开始，递归遍历子目录并累加文件大小。
代码实现
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define MAX_DIRS 201 // 目录ID范围[1, 200]
typedef struct {
int file_size; // 文件大小
int child_count; // 子目录数量
int children[11]; // 子目录列表（最多10个子目录）
} Directory;
Directory dirs[MAX_DIRS]; // 目录信息数组（索引即目录ID）
int initialized[MAX_DIRS] = {
0}; // 标记目录是否已初始化
// 辅助函数：去除字符串首尾空格
void trim(char *str) {
int start = 0, end = strlen(str) - 1;
while (isspace((unsigned char)str[start])) start++;
while (end >= start && isspace((unsigned char)str[end])) end--;
str[end + 1] = '';
memmove(str, str + start, end - start + 2);
}
// 解析目录行数据
void parse_directory_line(char *line) {
char *token;
int dir_id, file_size;
// 提取目录ID
token = strtok(line, " ");
dir_id = atoi(token);
// 提取文件大小
token = strtok(NULL, " ");
file_size = atoi(token);
// 提取子目录列表部分
token = strtok(NULL, "(");
token = strtok(NULL, ")"); // 获取括号内的内容
trim(token);
// 初始化目录结构体
dirs[dir_id].file_size = file_size;
dirs[dir_id].child_count = 0;
// 处理子目录列表
if (strlen(token) > 0) {
char *child_token = strtok(token, ",");
while (child_token != NULL) {
trim(child_token);
int child_id = atoi(child_token);
dirs[dir_id].children[dirs[dir_id].child_count++] = child_id;
child_token = strtok(NULL, ",");
}
}
initialized[dir_id] = 1; // 标记为已初始化
}
// 递归计算总大小
int calculate_total_size(int dir_id) {
if (!initialized[dir_id]) return 0; // 防止无效目录
int sum = dirs[dir_id].file_size;
for (int i = 0; i < dirs[dir_id].child_count; i++) {
sum += calculate_total_size(dirs[dir_id].children[i]);
}
return sum;
}
int main() {
int M, N;
char line[1000];
// 读取M和N
fgets(line, sizeof(line), stdin);
sscanf(line, "%d %d", &M, &N);
// 读取M行目录数据
for (int i = 0; i < M; i++) {
fgets(line, sizeof(line), stdin);
trim(line);
parse_directory_line(line);
}
// 计算结果并输出
printf("%d
", calculate_total_size(N));
return 0;
}
代码解析
数据结构：
typedef struct {
int file_size; // 当前目录的文件大小
int child_count; // 子目录数量
int children[11]; // 存储子目录ID（预留1个位置防止溢出）
} Directory;
使用固定大小的 children 数组存储子目录 ID，题目限定子目录最多 10 个。
输入处理：
fgets 逐行读取输入，sscanf 解析 M 和 N。
trim(line) 去除每行首尾空格，确保后续解析正确。
解析目录信息：
strtok 按空格和括号分割字符串，提取目录 ID、文件大小和子目录列表。
子目录列表通过 strtok 按逗号分割，转换为整数存入结构体。
递归计算：
calculate_total_size 递归遍历所有子目录，累加文件大小。
initialized 数组确保只有有效目录参与计算。
综合分析
高效的数据结构：
目录 ID 直接作为数组索引，查询复杂度为 O(1)。
固定大小的 children 数组避免动态内存管理的复杂性。
健壮性：
trim 函数处理输入中的多余空格。
initialized 标记防止未初始化的目录被访问。
内存安全：
避免动态内存分配，减少内存泄漏风险。
固定大小的数组严格遵循题目约束（子目录最多 10 个）。
时间复杂度：
每个目录仅访问一次，总时间复杂度为 O(M)，完全满足题目规模。
示例测试
输入1：
3 1
3 15 ()
1 20 (2)
2 10 (3)
解析：
目录1的子目录是2，目录2的子目录是3，目录3无子目录。
计算过程：
calculate_total_size(1) → 20 + 10 + 15 = 45
输入2：
4 2
4 20 ()
5 30 ()
2 10 (4,5)
1 40 ()
解析：
目录2的子目录是4和5。
计算过程：
calculate_total_size(2) → 10 + 20 + 30 = 60
总结
通过数组直接索引目录 ID，结合递归遍历子目录，C 语言实现兼顾效率和代码简洁性。输入处理充分考虑了格式的灵活性，适合题目要求，是 C 语言场景下的最优方案。
GO
题目分析
题目要求计算指定目录及其所有子目录的文件大小总和。每个目录信息以 目录id 文件大小 (子目录列表) 的格式给出，我们需要解析输入并递归累加目标目录及其所有子目录的文件大小。
解决思路
输入解析：逐行读取输入，提取目录 ID、文件大小和子目录列表。
数据结构：使用 map 存储目录的文件大小和子目录列表。
递归计算：从目标目录开始，递归遍历所有子目录，累加文件大小总和。
代码实现
package main
import (
"bufio"
"fmt"
"os"
"regexp"
"strconv"
"strings"
)
func main() {
scanner := bufio.NewScanner(os.Stdin)
// 读取第一行的 M 和 N
scanner.Scan()
firstLine := scanner.Text()
var M, N int
fmt.Sscanf(firstLine, "%d %d", &M, &N)
// 初始化存储结构
sizeMap := make(map[int]int) // 目录ID -> 文件大小
childrenMap := make(map[int][]int) // 目录ID -> 子目录ID列表
// 正则表达式用于解析目录行数据
re := regexp.MustCompile(`^(d+)s+(d+)s+((.*))$`)
// 读取 M 行目录数据
for i := 0; i < M; i++ {
scanner.Scan()
line := strings.TrimSpace(scanner.Text())
// 正则匹配提取目录信息
matches := re.FindStringSubmatch(line)
if matches == nil {
continue // 输入格式错误（根据题目描述，输入是合法的）
}
// 解析目录ID和文件大小
dirID, _ := strconv.Atoi(matches[1])
fileSize, _ := strconv.Atoi(matches[2])
childrenStr := matches[3] // 子目录列表部分（如 "2,3"）
// 处理子目录字符串
var children []int
if childrenStr != "" {
childTokens := strings.Split(childrenStr, ",")
for _, token := range childTokens {
childID, _ := strconv.Atoi(strings.TrimSpace(token))
children = append(children, childID)
}
}
// 存入map
sizeMap[dirID] = fileSize
childrenMap[dirID] = children
}
// 递归计算总大小
var calculateTotalSize func(int) int
calculateTotalSize = func(dirID int) int {
sum := sizeMap[dirID]
for _, childID := range childrenMap[dirID] {
sum += calculateTotalSize(childID)
}
return sum
}
// 输出结果
fmt.Println(calculateTotalSize(N))
}
代码解析
输入处理：
bufio.NewScanner 用于逐行读取输入。
fmt.Sscanf 解析第一行的 M 和 N。
数据结构：
sizeMap 和 childrenMap 是 map[int]int 和 map[int][]int，用于存储目录的文件大小和子目录列表。
正则表达式：
regexp.MustCompile 定义正则模式，精准提取目录信息的三部分（ID、文件大小、子目录列表）。
子目录处理：
strings.Split 按逗号分割子目录字符串，strings.TrimSpace 处理可能的空格。
递归计算：
calculateTotalSize 闭包递归遍历子目录，累加文件大小总和。
综合分析
精准的正则匹配：直接提取目录信息的三部分，避免空格干扰。
高效的递归：天然适合树形结构，代码简洁易懂。
健壮性：
TrimSpace 处理子目录字符串中的空格。
正则表达式确保输入格式正确性。
时间复杂度：每个目录仅访问一次，时间复杂度为 O(M)。
示例测试
输入1：
3 1
3 15 ()
1 20 (2)
2 10 (3)
解析：
目录1的子目录是2，目录2的子目录是3，目录3无子目录。
计算过程：
calculateTotalSize(1) → 20 + 10 + 15 = 45
输入2：
4 2
4 20 ()
5 30 ()
2 10 (4,5)
1 40 ()
解析：
目录2的子目录是4和5。
计算过程：
calculateTotalSize(2) → 10 + 20 + 30 = 60
总结
通过正则表达式精准解析输入，结合递归遍历目录树，Go 代码在保证性能的同时，完美适配题目要求。map 结构提供了高效的查询能力，是 Go 语言场景下的最优方案。
本文发表于【纪元A梦】
暂无评论内容