在系统中查找重复文件 图解题解

这道题到底在问什么

输入

paths=[ "root/a 1.txt(abcd) 2.txt(efgh)", "root/c 3.txt(abcd)" ]

输出

[ ["root/a/1.txt","root/c/3.txt"] ] （abcd 内容相同）

输入

paths=[ "root/a 1.txt(x)", "root/b 2.txt(y)" ]

输出

[] （内容各不相同）

最优解：一步一步想明白

1. 3记住这套「内容当 key、路径进桶、最后挑 ≥2 的桶」，下面每一帧都在套它。
2. 4一共 5 条目录信息，拍平后是 6 个文件。桶现在是空的，等着内容相同的文件落进同一个桶。
3. 5先看拆一个文件的招式:找到左括号，前面是文件名，括号里是内容。再把目录拼上文件名，就得到完整路径 root/a/1.txt。下面对每个文件都这么拆。
4. 6解析出第 1 个文件 root/a/1.txt，内容是 abcd。这是个没见过的新内容，下一帧给它开一个新桶。
5. 7root/a/1.txt 进了 0 号桶（内容 abcd），这个桶现在有 1 个文件。内容一样的文件，会一直往同一个桶里堆。
6. 8解析出第 2 个文件 root/a/2.txt，内容是 efgh。这是个没见过的新内容，下一帧给它开一个新桶。
7. 9root/a/2.txt 进了 1 号桶（内容 efgh），这个桶现在有 1 个文件。内容一样的文件，会一直往同一个桶里堆。
8. 10解析出第 3 个文件 root/c/3.txt，内容是 abcd。这个内容之前出现过，对应的桶亮起来了，下一帧把当前路径也丢进去。
9. 11root/c/3.txt 进了 0 号桶（内容 abcd），这个桶现在有 2 个文件。内容一样的文件，会一直往同一个桶里堆。
10. 12解析出第 4 个文件 root/c/d/4.txt，内容是 efgh。这个内容之前出现过，对应的桶亮起来了，下一帧把当前路径也丢进去。
11. 13root/c/d/4.txt 进了 1 号桶（内容 efgh），这个桶现在有 2 个文件。内容一样的文件，会一直往同一个桶里堆。
12. 14解析出第 5 个文件 root/4.txt，内容是 efgh。这个内容之前出现过，对应的桶亮起来了，下一帧把当前路径也丢进去。
13. 15root/4.txt 进了 1 号桶（内容 efgh），这个桶现在有 3 个文件。内容一样的文件，会一直往同一个桶里堆。
14. 16解析出第 6 个文件 root/e/5.txt，内容是 zzzz。这是个没见过的新内容，下一帧给它开一个新桶。
15. 17root/e/5.txt 进了 2 号桶（内容 zzzz），这个桶现在有 1 个文件。内容一样的文件，会一直往同一个桶里堆。
16. 186 个文件都归桶了。可以看到 abcd 桶和 efgh 桶各装了好几个路径，zzzz 桶只有一个。接下来就看哪些桶里装了不止一个。
17. 19归桶完成，现在从头到尾扫每个桶。判定规则很简单:桶里装了至少两个文件，这一桶就是一组重复;只装了一个的，跳过。
18. 20看 0 号桶，内容 abcd，里面有 2 个文件:root/a/1.txt、root/c/3.txt。数量到了 2 个，这就是一组重复文件，收进答案。
19. 21看 1 号桶，内容 efgh，里面有 3 个文件:root/a/2.txt、root/c/d/4.txt、root/4.txt。数量到了 2 个，这就是一组重复文件，收进答案。
20. 22看 2 号桶，内容 zzzz，里面只有 1 个文件 root/e/5.txt。孤零零一个，凑不成重复组，跳过它。
21. 23扫完三个桶，桶 0 和桶 1 都满足条件，一共 2 组重复文件;zzzz 那桶被跳过。
22. 24最终答案是这 2 组:root/a/1.txt、root/c/3.txt 和 root/a/2.txt、root/c/d/4.txt、root/4.txt。每一组里的文件内容都完全相同，正是题目要找的重复文件。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
from string import *
from operator import *
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def findDuplicate(self, paths: List[str]) -> List[List[str]]:
        groups = defaultdict(list)
        for entry in paths:
            parts = entry.split()
            root = parts[0]
            for file in parts[1:]:
                name, rest = file.split("(", 1)
                content = rest[:-1]
                groups[content].append(root + "/" + name)
        ans = [sorted(v) for v in groups.values() if len(v) > 1]
        ans.sort()
        return ans

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
    vector<vector<string>> findDuplicate(vector<string>& paths) {
        unordered_map<string, vector<string>> groups;
        for (auto& entry : paths) {
            stringstream ss(entry);
            string root, file;
            ss >> root;
            while (ss >> file) {
                int p = file.find('(');
                string name = file.substr(0, p);
                string content = file.substr(p + 1, file.size() - p - 2);
                groups[content].push_back(root + "/" + name);
            }
        }
        vector<vector<string>> ans;
        for (auto& [_, v] : groups) if (v.size() > 1) {
            sort(v.begin(), v.end());
            ans.push_back(v);
        }
        sort(ans.begin(), ans.end());
        return ans;
    }
};

import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    public List<List<String>> findDuplicate(String[] paths) {
        Map<String, List<String>> groups = new HashMap<>();
        for (String entry : paths) {
            String[] parts = entry.split(" ");
            String root = parts[0];
            for (int i = 1; i < parts.length; i++) {
                String file = parts[i];
                int p = file.indexOf('(');
                String name = file.substring(0, p);
                String content = file.substring(p + 1, file.length() - 1);
                groups.computeIfAbsent(content, k -> new ArrayList<>()).add(root + "/" + name);
            }
        }
        List<List<String>> ans = new ArrayList<>();
        for (List<String> v : groups.values()) if (v.size() > 1) {
            Collections.sort(v);
            ans.add(v);
        }
        Collections.sort(ans, (a, b) -> {
            int n = Math.min(a.size(), b.size());
            for (int i = 0; i < n; i++) {
                int c = a.get(i).compareTo(b.get(i));
                if (c != 0) return c;
            }
            return a.size() - b.size();
        });
        return ans;
    }
}

复杂度

面试官可能追问