Leetcode力扣秋招刷题路-0609-Toy模板网

这篇具有很好参考价值的文章主要介绍了Leetcode力扣秋招刷题路-0609。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

从0开始的秋招刷题路，记录下所刷每道题的题解，帮助自己回顾总结

609. 在系统中查找重复文件

给你一个目录信息列表 paths ，包括目录路径，以及该目录中的所有文件及其内容，请你按路径返回文件系统中的所有重复文件。答案可按任意顺序返回。

一组重复的文件至少包括两个具有完全相同内容的文件。

输入列表中的单个目录信息字符串的格式如下：

“root/d1/d2/…/dm f1.txt(f1_content) f2.txt(f2_content) … fn.txt(fn_content)”
这意味着，在目录 root/d1/d2/…/dm 下，有 n 个文件 ( f1.txt, f2.txt … fn.txt ) 的内容分别是 ( f1_content, f2_content … fn_content ) 。注意：n >= 1 且 m >= 0 。如果 m = 0 ，则表示该目录是根目录。

输出是由重复文件路径组构成的列表。其中每个组由所有具有相同内容文件的文件路径组成。文件路径是具有下列格式的字符串：
“directory_path/file_name.txt”

示例 1：
输入：paths = [“root/a 1.txt(abcd) 2.txt(efgh)”,“root/c 3.txt(abcd)”,“root/c/d 4.txt(efgh)”,“root 4.txt(efgh)”]
输出：[[“root/a/2.txt”,“root/c/d/4.txt”,“root/4.txt”],[“root/a/1.txt”,“root/c/3.txt”]]

示例 2：
输入：paths = [“root/a 1.txt(abcd) 2.txt(efgh)”,“root/c 3.txt(abcd)”,“root/c/d 4.txt(efgh)”]
输出：[[“root/a/2.txt”,“root/c/d/4.txt”],[“root/a/1.txt”,“root/c/3.txt”]]

提示：
1 <= paths.length <= $2 * 10^4$
1 <= paths[i].length <= 3000
1 <= sum(paths[i].length) <= $5 * 10^5$
paths[i] 由英文字母、数字、字符 ‘/’、‘.’、‘(’、‘)’ 和 ’ ’ 组成
你可以假设在同一目录中没有任何文件或目录共享相同的名称。
你可以假设每个给定的目录信息代表一个唯一的目录。目录路径和文件信息用单个空格分隔。

进阶：
假设您有一个真正的文件系统，您将如何搜索文件？广度搜索还是宽度搜索？
如果文件内容非常大（GB级别），您将如何修改您的解决方案？
如果每次只能读取 1 kb 的文件，您将如何修改解决方案？
修改后的解决方案的时间复杂度是多少？其中最耗时的部分和消耗内存的部分是什么？如何优化？
如何确保您发现的重复文件不是误报？

思路和算法
给定的数组 paths 中的每个元素表示一个目录的路径以及该目录中的所有文件的文件名和文件内容。如果一个元素包含用空格分隔的 m 项，则可以将该元素使用空格作为分隔符创建长度为 m 的数组，数组中的第 0 项为目录路径，其余 m−1 项分别为该目录中的每个文件的文件信息，包括文件名和文件内容，可以根据数组中的每个元素得到每个文件的绝对路径和文件内容。

为了找到重复文件，需要找到每种文件内容对应的文件列表，并判断文件列表中的文件个数，如果文件个数大于 1 则该文件列表为一组重复文件。可以使用哈希表记录每种文件内容对应的文件列表。

由于文件系统中的任意两个目录的路径都不同，任意两个文件的绝对路径都不同，因此不需要对目录的路径和文件的绝对路径做排重操作，使用列表表示每种文件内容的文件列表即可。

对于数组 paths 中的每个元素，首先将该元素使用空格作为分隔符创建文件数组，然后对文件数组中的除了第 0 项以外的每一项得到文件的绝对路径和文件内容，在哈希表中将文件的绝对路径添加到文件内容的文件列表中。

遍历结束数组 paths 之后，遍历哈希表，对于哈希表中的每种文件内容，如果对应的文件列表中的文件个数大于 1，则将该文件列表添加到结果中。

代码

class Solution {
    public List<List<String>> findDuplicate(String[] paths) {
        Map<String, List<String>> map = new HashMap<String, List<String>>();
        for (String path : paths) {
            String[] array = path.split(" ");
            StringBuffer directoryBuffer = new StringBuffer(array[0]);
            if (directoryBuffer.charAt(directoryBuffer.length() - 1) != '/') {
                directoryBuffer.append('/');
            }
            String directory = directoryBuffer.toString();
            int length = array.length;
            for (int i = 1; i < length; i++) {
                String fileNameContent = array[i];
                int fileNameContentLength = fileNameContent.length();
                int leftParenthesisIndex = -1;
                StringBuffer fileNameBuffer = new StringBuffer();
                for (int j = 0; j < fileNameContentLength && leftParenthesisIndex < 0; j++) {
                    char c = fileNameContent.charAt(j);
                    if (c == '(') {
                        leftParenthesisIndex = j;
                    } else {
                        fileNameBuffer.append(c);
                    }
                }
                String fileName = fileNameBuffer.toString();
                String content = fileNameContent.substring(leftParenthesisIndex + 1, fileNameContentLength - 1);
                String completeFileName = directory + fileName;
                map.putIfAbsent(content, new ArrayList<String>());
                map.get(content).add(completeFileName);
            }
        }
        List<List<String>> duplicates = new ArrayList<List<String>>();
        Set<Map.Entry<String, List<String>>> entries = map.entrySet();
        for (Map.Entry<String, List<String>> entry : entries) {
            String content = entry.getKey();
            List<String> files = entry.getValue();
            if (files.size() > 1) {
                duplicates.add(files);
            }
        }
        return duplicates;
    }
}

复杂度分析
时间复杂度：O(n)，其中 n 是文件系统中的文件总数。遍历文件系统中的全部文件并将每种文件内容和对应的文件列表存入哈希表，需要 O(n) 的时间，遍历哈希表得到结果也需要 O(n) 的时间。这里将字符串操作的时间视为 O(1)。

空间复杂度：O(n)，其中 n 是文件系统中的文件总数。空间复杂度主要取决于哈希表，哈希表中需要存储每种文件内容对应的文件列表，空间是 O(n)。这里将字符串占用的空间视为 O(1)。

进阶问题答案
假设给你一个真正的文件系统，你将如何搜索文件？深度优先搜索还是广度优先搜索？

深度优先搜索和广度优先搜索的时间复杂度相同，因此应该根据空间复杂度决定使用哪种搜索方法。如果文件系统树结构的深度是 d，平均分支数是 f（即树结构中的每个目录结点平均有 f 个子结点），则深度优先搜索的空间复杂度是 O(d)，广度优先搜索的空间复杂度是 $O(f^d)$ 。大多数情况下，O(d) 优于 $O(f^d)$ ，因此大多数情况下应该使用深度优先搜索。

如果文件内容非常大（GB 级别），你将如何修改你的解决方案？

如果文件内容非常大，则不能一次性存储文件的完整内容，因此需要将文件内容分块存储，并存储元数据，元数据包括文件名、文件大小、各分块的偏移量、各分块的哈希值等。其中，一个分块的哈希值等于该分块的内容使用特定哈希函数计算得到的结果，每个文件的所有分块的哈希值计算都使用同一个哈希函数。如果两个文件的内容相同，则这两个文件的大小一定也相同。因此，比较两个文件的内容是否相同时，首先比较两个文件的大小是否相同，如果大小不同则内容一定不同，如果大小相同再依次比较每个分块的哈希值是否相同，只要有一个分块的哈希值不同，则两个文件的内容不同，只有当每个分块的哈希值都相同时，才能认为两个文件的内容可能相同。使用哈希值进行比较虽然可以降低内存空间（只需要将哈希值存入内存，不需要将文件内容直接存入内存），但是可能存在误报的情况，问题 5 将提供解决方案。

如果每次只能读取 1 KB 的文件，你将如何修改你的解决方案？

每次只能读取 1 KB 的文件，则每个分块的大小最多为 1 KB，因此使用问题 2 的解决方案，将每个分块的大小设为 1 KB。

修改后的解决方案的时间复杂度是多少？其中最消耗时间的部分和最消耗内存的部分是什么？如何优化？

如果文件系统中的文件个数是 n，每个文件的平均大小是 k，则时间复杂度是 $O(kn^2)$ 。对于每个文件需要 O(k) 的时间计算元数据，其中计算每个分块哈希值的时间复杂度最高，共需要 O(kn) 的时间计算元数据。每两个文件之间都需要比较，比较次数是 $\dfrac{n(n - 1)}{2}$ ，每次比较首先比较文件大小，然后比较每个分块的哈希值，因此最坏情况下每次比较的时间复杂度是 O(k)，总时间复杂度是 $O(kn^2)$ 。最消耗时间和内存的部分是哈希值的计算和存储。由于文件个数 nnn 和比较次数 $\dfrac{n(n - 1)}{2}$ 无法减少，因此可以优化的方面只有哈希值的计算。在条件允许的情况下，将每个分块的大小增加，即可减少分块个数。