解题思路
本题在**文件路径前缀树(逻辑上按 / 分段)**上做统计:对每个文件,把它的大小累加到「目标目录 target 的一级子项」上。
- 目标是否存在:若存在某个文件路径
p 满足 p == target 或 p 以 target + '/' 为前缀,则认为 target 在文件系统中出现;否则返回空列表。
- 一级子项划分:对满足
p 以 target + '/' 开头的文件,令相对路径 rel = p[len(target)+1:]。若 rel 中不含 /,则该文件本身就是一级子项,累加到 p;否则一级子项为 target + '/' + rel 的第一段路径前缀。
- 目录大小:题意规定目录占用为其内部所有文件大小之和;本题输入只给出文件,因此「一级子目录」的大小等于所有路径以该子目录为前缀的文件大小之和,与上面的累加方式一致。
- 答案:在所有一级子项的聚合大小中取最大值,将所有达到最大值的子项路径按字典序升序输出。若目标存在但没有任何子路径文件,则返回空列表。
P4724.空间占用计算(100分)
题目描述
员工 A 的磁盘空间经常被耗尽,他需要找到占用空间最大的目录或文件,然后决定如何清理文件释放空间。
给定某一目录,请编写程序帮助他统计该目录内一级子目录和文件的占用空间,并返回目标目录一级子项(文件或子目录)中占用空间最大的项。
规则说明
- 目录占用空间为其内部所有文件 Size 的总和,且目录本身 Size 为 0。
- 目录深度不高于 7 层,目录或文件名总长度不超过 128 字节。
- 当存在多个子项占用空间均为最大时,多个子项采用字符升序排列。
- 目标目录不在文件系统中时(输入路径前缀匹配不到任何路径),返回空列表。
输入描述
输入:
参数 1:要进行统计的目标目录。
参数 2:文件系统内的文件列表。
参数 3:文件 Size 列表,该列表中的数据和文件列表存在一一对应关系。
输出描述
输出:
目标目录一级子项(文件或子目录)中占用空间最大的项组成的列表。
样例1
输入
"/dir1/dir2-1", ["/dir0/dir1-1/file1-1", "/dir1/dir1-1/file1-1", "/dir1/dir2-1/file3-1", "/dir1/dir2-1/file3-2", "/dir1/dir2-1/dir3-1/file4-1"], [8192, 81920, 2048, 8192, 1024]
输出
["/dir1/dir2-1/file3-2"]
说明
/dir1/dir2−1 下共有三个一级子项 file3−1、file3−2、dir3−1,它们的占用空间统计如下:
- file3−1:2048
- file3−2:8192
- dir3−1:1024,其内部所有文件的 Size 之和,由于内部只有一个文件 file4−1,因此和 file4−1 的 Size 一致。
其中 file3−2 占用的空间最大,因此返回 ["/dir1/dir2−1/file3−2"]。
样例2
输入
"/dir1", ["/dir0/dir2-1/file3-1", "/dir1/dir2-1/file3-1", "/dir1/dir2-1/file3-2", "/dir1/dir2-2/file3-3", "/dir1/file2-3"], [10240, 4096, 8192, 10240, 8192]
输出
["/dir1/dir2-1"]
说明
/dir1 下共有三个一级子项 dir2−1、dir2−2、file2−3,它们的占用空间如下:
- dir2−1:12288,其内部所有文件的 Size 之和,即 file3−1 和 file3−2 的 Size 相加,结果为 12288。
- dir2−2:10240,其内部所有文件的 Size 之和,即 file3−3 的 Size 为 10240。
- file2−3:8192。
其中 dir2−1 占用的空间最大,因此返回 ["/dir1/dir2−1"]。
样例3
输入
"/dir1", ["/dir1/dir1/file1", "/dir1/dir1/file2", "/dir1/dir2/file3"], [1024, 2048, 3072]
输出
["/dir1/dir1", "/dir1/dir2"]
说明
/dir1 下共有两个一级子项 dir1、dir2,它们的占用空间如下:
- dir1:3072,其内部所有文件的 Size 之和,即 file1 和 file2 的 Size 之和为 3072。
- dir2:3072,其内部所有文件的 Size 之和,即 file3 的 Size 为 3072。
由于 dir1 和 dir2 占用的空间一致,且为最大,因此需要对这两个子项进行升序排列后返回,返回结果为 ["/dir1/dir1","/dir1/dir2"]。