2025A-文件目录大小-刷题笔记

问题描述

小哀需要计算一个文件目录及其所有子目录的总大小。每个目录的数据格式为：

目录id 本目录大小 (子目录id列表)

例如：1 20 (2,3) 表示目录1的大小为20，包含两个子目录2和3。

输入格式

第一行：两个整数M和N，分别表示目录总数和待查询的目录id

• 1 ≤ M ≤ 100 (目录总数)
• 1 ≤ N ≤ 200 (目录id)

接下来M行，每行表示一个目录：

• 目录id：[1, 200]
• 目录大小：[1, 1000]
• 子目录数量：[0, 10]

输出格式

一个整数，表示待查询目录及其所有子目录的大小之和。

样例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

题解

这道题可以用DFS或BFS解决：

1. 构建目录树：

   • 使用Map存储每个目录的大小
   • 使用Map存储每个目录的子目录列表

2. 遍历目录树：

   • 从目标目录开始遍历
   • 累加当前目录和所有子目录的大小

参考代码

def solve(dirs, sizes, target):
    # 使用栈实现DFS
    total = 0
    stack = [target]
    
    while stack:
        curr = stack.pop()
        # 累加当前目录大小
        if curr in sizes:
            total += sizes[curr]
            # 将子目录加入栈
            stack.extend(dirs.get(curr, []))
    
    return total

# 处理输入
M, N = map(int, input().split())

# 构建目录树
dirs = {}   # 存储子目录列表
sizes = {}  # 存储目录大小

for _ in range(M):
    # 解析目录信息
    line = input().split()
    dir_id = line[0]
    size = int(line[1])
    children = []
    
    # 解析子目录列表
    if line[2] != "()":
        children = line[2][1:-1].split(",")
    
    dirs[dir_id] = children
    sizes[dir_id] = size

# 计算总大小
print(solve(dirs, sizes, str(N)))

#include <iostream>
#include <vector>
#include <map>
#include <stack>
#include <string>
using namespace std;

class Solution {
public:
    int solve(map<int, vector<int>>& dirs, map<int, int>& sizes, int target) {
        int total = 0;
        stack<int> stk;
        stk.push(target);
        
        while (!stk.empty()) {
            int curr = stk.top();
            stk.pop();
            
            // 累加当前目录大小
            if (sizes.count(curr)) {
                total += sizes[curr];
                // 将子目录加入栈