子域名访问计数 图解题解

这道题到底在问什么

输入

cpdomains = ["900 g.mail.com","50 yahoo.com","1 intel.mail.com","5 wiki.org"]

输出

["901 mail.com","50 yahoo.com","900 g.mail.com","5 wiki.org","5 org","1 intel.mail.com","951 com"]（顺序不限）

最优解：一步一步想明白

1. 3两步循环：外层逐条记录、内层逐级后缀。每个后缀都把这条记录的次数加上去，靠哈希表自动把相同域名的次数累加在一起。
2. 4count = {}（空）开始前：哈希表 count 为空，还没处理任何记录。
3. 5cnt = 900 ; d = g.mail.com取第 1 条记录 "900 g.mail.com"：次数 cnt=900，域名 d=g.mail.com。
4. 6后缀 = [g.mail.com , mail.com , com]把 g.mail.com 按点号切成各级后缀：g.mail.com / mail.com / com。每一个都要加上 900。
5. 7count["g.mail.com"] : 0 + 900 = 900给后缀 g.mail.com 加上 900：原来 0 → 现在 900（第一次出现，新建桶）。
6. 8count["mail.com"] : 0 + 900 = 900给后缀 mail.com 加上 900：原来 0 → 现在 900（第一次出现，新建桶）。
7. 9count["com"] : 0 + 900 = 900给后缀 com 加上 900：原来 0 → 现在 900（第一次出现，新建桶）。
8. 10cnt = 50 ; d = yahoo.com取第 2 条记录 "50 yahoo.com"：次数 cnt=50，域名 d=yahoo.com。
9. 11后缀 = [yahoo.com , com]把 yahoo.com 按点号切成各级后缀：yahoo.com / com。每一个都要加上 50。
10. 12count["yahoo.com"] : 0 + 50 = 50给后缀 yahoo.com 加上 50：原来 0 → 现在 50（第一次出现，新建桶）。
11. 13count["com"] : 900 + 50 = 950给后缀 com 加上 50：原来 900 → 现在 950（已存在，累加）。
12. 14cnt = 1 ; d = intel.mail.com取第 3 条记录 "1 intel.mail.com"：次数 cnt=1，域名 d=intel.mail.com。
13. 15后缀 = [intel.mail.com , mail.com , com]把 intel.mail.com 按点号切成各级后缀：intel.mail.com / mail.com / com。每一个都要加上 1。
14. 16count["intel.mail.com"] : 0 + 1 = 1给后缀 intel.mail.com 加上 1：原来 0 → 现在 1（第一次出现，新建桶）。
15. 17count["mail.com"] : 900 + 1 = 901给后缀 mail.com 加上 1：原来 900 → 现在 901（已存在，累加）。
16. 18count["com"] : 950 + 1 = 951给后缀 com 加上 1：原来 950 → 现在 951（已存在，累加）。
17. 19cnt = 5 ; d = wiki.org取第 4 条记录 "5 wiki.org"：次数 cnt=5，域名 d=wiki.org。
18. 20后缀 = [wiki.org , org]把 wiki.org 按点号切成各级后缀：wiki.org / org。每一个都要加上 5。
19. 21count["wiki.org"] : 0 + 5 = 5给后缀 wiki.org 加上 5：原来 0 → 现在 5（第一次出现，新建桶）。
20. 22count["org"] : 0 + 5 = 5给后缀 org 加上 5：原来 0 → 现在 5（第一次出现，新建桶）。
21. 23扫描结束 ; 共 7 个域名所有记录处理完。哈希表里每个域名对应的就是它的总访问次数，把它们组成结果即可。

⚠️ 容易写错的地方

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

def subdomainVisits(cpdomains):
    from collections import defaultdict
    count = defaultdict(int)
    for cp in cpdomains:
        cnt_s, dom = cp.split()      # 拆出次数和域名
        cnt = int(cnt_s)
        parts = dom.split('.')
        for i in range(len(parts)):  # 逐级后缀
            suffix = '.'.join(parts[i:])
            count[suffix] += cnt
    return [f'{c} {d}' for d, c in count.items()]

vector<string> subdomainVisits(vector<string>& cpdomains){
    unordered_map<string,int> count;
    for (auto& cp : cpdomains) {
        int sp = cp.find(' ');
        int cnt = stoi(cp.substr(0, sp));
        string dom = cp.substr(sp + 1);
        for (int i = 0; i < dom.size(); i++)
            if (i == 0 || dom[i-1] == '.')
                count[dom.substr(i)] += cnt;   // 每个后缀
    }
    vector<string> res;
    for (auto& [d, c] : count) res.push_back(to_string(c)+" "+d);
    return res;
}

public List<String> subdomainVisits(String[] cpdomains) {
    Map<String,Integer> count = new HashMap<>();
    for (String cp : cpdomains) {
        int sp = cp.indexOf(' ');
        int cnt = Integer.parseInt(cp.substring(0, sp));
        String dom = cp.substring(sp + 1);
        for (int i = 0; i < dom.length(); i++)
            if (i == 0 || dom.charAt(i-1) == '.')
                count.merge(dom.substring(i), cnt, Integer::sum);
    }
    List<String> res = new ArrayList<>();
    count.forEach((d, c) -> res.add(c + " " + d));
    return res;
}

复杂度

面试官可能追问