题目描述
思路解析动画文字版
两步循环:外层逐条记录、内层逐级后缀。每个后缀都把这条记录的次数加上去,靠哈希表自动把相同域名的次数累加在一起。
初始化:count = {}:开始前:哈希表 count 为空,还没处理任何记录。
读第 1 条:g.mail.com,次数 900:取第 1 条记录 "900 g.mail.com":次数 cnt=900,域名 d=g.mail.com。
拆后缀:g.mail.com · mail.com · com:把 g.mail.com 按点号切成各级后缀:g.mail.com / mail.com / com。每一个都要加上 900。
count["g.mail.com"] += 900 → 900:给后缀 g.mail.com 加上 900:原来 0 → 现在 900(第一次出现,新建桶)。
count["mail.com"] += 900 → 900:给后缀 mail.com 加上 900:原来 0 → 现在 900(第一次出现,新建桶)。
count["com"] += 900 → 900:给后缀 com 加上 900:原来 0 → 现在 900(第一次出现,新建桶)。
读第 2 条:yahoo.com,次数 50:取第 2 条记录 "50 yahoo.com":次数 cnt=50,域名 d=yahoo.com。
拆后缀:yahoo.com · com:把 yahoo.com 按点号切成各级后缀:yahoo.com / com。每一个都要加上 50。
count["yahoo.com"] += 50 → 50:给后缀 yahoo.com 加上 50:原来 0 → 现在 50(第一次出现,新建桶)。
count["com"] += 50 → 950:给后缀 com 加上 50:原来 900 → 现在 950(已存在,累加)。
读第 3 条:intel.mail.com,次数 1:取第 3 条记录 "1 intel.mail.com":次数 cnt=1,域名 d=intel.mail.com。
拆后缀:intel.mail.com · mail.com · com:把 intel.mail.com 按点号切成各级后缀:intel.mail.com / mail.com / com。每一个都要加上 1。
count["intel.mail.com"] += 1 → 1:给后缀 intel.mail.com 加上 1:原来 0 → 现在 1(第一次出现,新建桶)。
count["mail.com"] += 1 → 901:给后缀 mail.com 加上 1:原来 900 → 现在 901(已存在,累加)。
count["com"] += 1 → 951:给后缀 com 加上 1:原来 950 → 现在 951(已存在,累加)。
读第 4 条:wiki.org,次数 5:取第 4 条记录 "5 wiki.org":次数 cnt=5,域名 d=wiki.org。
拆后缀:wiki.org · org:把 wiki.org 按点号切成各级后缀:wiki.org / org。每一个都要加上 5。
count["wiki.org"] += 5 → 5:给后缀 wiki.org 加上 5:原来 0 → 现在 5(第一次出现,新建桶)。
count["org"] += 5 → 5:给后缀 org 加上 5:原来 0 → 现在 5(第一次出现,新建桶)。
处理完毕:count 即最终答案:所有记录处理完。哈希表里每个域名对应的就是它的总访问次数,把它们组成结果即可。
三个高频追问:为何统计父域、怎么切后缀、为何用哈希表。
参考代码
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()]复杂度
- 时间:O(N·L),N 条记录、每条域名长度 L;切后缀并累加都与 L 成正比
- 空间:O(N·L),哈希表里最多存下所有出现过的域名(含各级父域)
易错点
面试追问把动画讲成自己的话
追问为什么要统计父域名?
追问怎么从 g.mail.com 切出所有父域?
追问为什么选哈希表而不是排序?
这道题到这就讲完了。动画和文字是同一套思路——别光看,关掉页面自己默写一遍。然后顺着主线继续:
总持续时间可被 60 整除的歌曲
LeetCode 1010 · 中等 · 沿着 哈希套路 继续往下推进
把这道题真正学会,再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解(全站陆续覆盖)
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告,记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法,几十万开发者在看的算法讲解
想成体系刷透这类套路?去图解算法专题