题目描述
思路解析动画文字版
下面 15 步动画会按主解代码推进,而不是泛泛讲题型。
1. 看输入:输入 cpdomains = ["100 a.b.com", "50 b.com"]。每条记录由次数和域名组成,访问一个域名时,它自身以及每一级父域名都要加上这个次数。
2. 思路:每个后缀就是一级父域名:核心:把域名按点拆成若干段,从第 i 段起拼回去得到的后缀,就是一级子域名或父域名。a.b.com 拆出 a.b.com、b.com、com 三个域,各加同样的次数。
3. 第1条:拆出 num 与 domain:处理第 1 条 item="100 a.b.com"。先按空格切一刀:次数 num=100,域名 domain=a.b.com。此时字典 cnt 还是空的。
4. domain 按点拆成 parts:把 domain=a.b.com 按点拆成 parts=[a, b, com],共 3 段。接下来从每个位置 i 起取后缀,得到一级父域名。
5. i=0:后缀 a.b.com,cnt 加 100:i=0,从第 0 段起拼回所有段,得到后缀 sub=a.b.com。cnt 里没有它,按 0 起算:cnt[a.b.com] = 0 + 100 = 100。
6. i=1:后缀 b.com,cnt 加 100:i=1,从第 1 段起拼回,得到后缀 sub=b.com。它也还没出现过,cnt[b.com] = 0 + 100 = 100。
7. i=2:后缀 com,cnt 加 100:i=2,最后一段单独成后缀 sub=com,cnt[com] = 0 + 100 = 100。第 1 条记录处理完,三个父域名各计 100。
8. 第1条处理完,看当前 cnt:第 1 条 "100 a.b.com" 处理完。cnt 里有 3 个域:a.b.com、b.com、com,各为 100。回到主循环处理下一条。
9. 第2条:拆出 num 与 domain:处理第 2 条 item="50 b.com"。按空格拆出次数 num=50,域名 domain=b.com。此前 cnt 里 b.com 与 com 已各有 100。
10. domain 按点拆成 parts:把 domain=b.com 按点拆成 parts=[b, com],共 2 段。同样从每个位置 i 起取后缀累加。
11. i=0:后缀 b.com,累加到 150:i=0,后缀 sub=b.com 已在 cnt 中且为 100,这次在原值上累加:cnt[b.com] = 100 + 50 = 150。这就是「父域名累加」的关键。
12. i=1:后缀 com,累加到 150:i=1,后缀 sub=com 也已存在,cnt[com] = 100 + 50 = 150。第 2 条处理完,b.com 与 com 都被累加成 150。
13. 两条都处理完,cnt 定型:两条记录都处理完。最终 cnt:a.b.com=100、b.com=150、com=150。b.com 和 com 各被两条记录命中而累加。
14. 构造返回格式:返回时把 cnt 每个键值对拼成 "次数 域名" 字符串,例如 a.b.com:100 拼成 "100 a.b.com"。
15. 返回最终结果:最终返回 ["100 a.b.com", "150 b.com", "150 com"]。题目允许任意顺序,长度等于 cnt 中不同域名的个数。
记住这题的代码骨架:题意约束先落到状态变量,再用循环或递归维护它。
参考代码
class Solution: def subdomainVisits(self, cpdomains): cnt = {} for item in cpdomains: num, domain = item.split() num = int(num) parts = domain.split('.') for i in range(len(parts)): sub = '.'.join(parts[i:]) cnt[sub] = cnt.get(sub, 0) + num return [str(v) + ' ' + k for k, v in cnt.items()]复杂度
- 时间复杂度:O(total chars),拆分域名
- 空间复杂度:O(total domains),计数字典
易错点
这道题到这就讲完了。动画和文字是同一套思路——别光看,关掉页面自己默写一遍。再去主线里挑下一道练手。
把这道题真正学会,再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解(全站陆续覆盖)
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告,记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法,几十万开发者在看的算法讲解
想成体系刷透这类套路?去图解算法专题