题目形容
这是 LeetCode 上的 811. 子域名拜访计数 ，难度为 中等。
Tag :「模仿」、「哈希表」
网站域名 "discuss.leetcode.com" 由多个子域名组成。顶级域名为 "com"，二级域名为 "leetcode.com"，最低一级为 "discuss.leetcode.com"。
当拜访域名 "discuss.leetcode.com" 时，同时也会隐式拜访其父域名 "leetcode.com" 以及 "com"。
计数配对域名 是遵循 "rep d1.d2.d3" 或 "rep d1.d2" 格局的一个域名示意，其中 rep 示意拜访域名的次数，d1.d2.d3 为域名自身。
例如，"9001 discuss.leetcode.com" 就是一个 计数配对域名，示意 discuss.leetcode.com 被拜访了 9001 次。
给你一个 计数配对域名 组成的数组 cpdomains，解析失去输出中每个子域名对应的 计数配对域名，并以数组模式返回。能够按 任意程序 返回答案。
示例 1：
输出：cpdomains = ["9001 discuss.leetcode.com"]
输入：["9001 leetcode.com","9001 discuss.leetcode.com","9001 com"]
解释：例子中仅蕴含一个网站域名："discuss.leetcode.com"。依照前文形容，子域名 "leetcode.com" 和 "com" 都会被拜访，所以它们都被拜访了 9001 次。示例 2：
输出：cpdomains = ["900 google.mail.com", "50 yahoo.com", "1 intel.mail.com", "5 wiki.org"]
输入：["901 mail.com","50 yahoo.com","900 google.mail.com","5 wiki.org","5 org","1 intel.mail.com","951 com"]
解释：依照前文形容，会拜访 "google.mail.com" 900 次，"yahoo.com" 50 次，"intel.mail.com" 1 次，"wiki.org" 5 次。而对于父域名，会拜访 "mail.com" 900 + 1 = 901 次，"com" 900 + 50 + 1 = 951 次，和 "org" 5 次。提醒：
- $1 <= cpdomain.length <= 100$
- $1 <= cpdomain[i].length <= 100$
cpdomain[i]会遵循"repi d1i.d2i.d3i"或"repi d1i.d2i"格局repi是范畴 $[1, 10^4]$ 内的一个整数- $d1_i$、$d2_i$ 和 $d3_i$ 由小写英文字母组成
哈希表
为了不便，咱们令 cpdomains 为 ss。
依据题意进行模仿：应用哈希表记录每个域名的总拜访次数，从前往后解决所有的 $ss[i]$。在解决某个 $ss[i]$ 时（记长度为 $n$，应用指针 idx 代指扫描到的游标位置），先通过指针扫描找到拜访数字局部 cnt = ss[i][0:idx]，而后「从后往前」解决 $ss[i]$ 的 $[idx + 1, n – 1]$ 局部，依照域名层级「从小到大」的程序进行截取，并累加拜访次数 cnt 到以后域名。
最初依据哈希表结构答案。
Java 代码：
class Solution {public List<String> subdomainVisits(String[] ss) {Map<String, Integer> map = new HashMap<>();
for (String s : ss) {int n = s.length(), idx = 0;
while (idx < n && s.charAt(idx) != ' ') idx++;
int cnt = Integer.parseInt(s.substring(0, idx));
int start = idx + 1; idx = n - 1;
while (idx >= start) {while (idx >= start && s.charAt(idx) != '.') idx--;
String cur = s.substring(idx + 1);
map.put(cur, map.getOrDefault(cur, 0) + cnt);
idx--;
}
}
List<String> ans = new ArrayList<>();
for (String key : map.keySet()) ans.add(map.get(key) + " " + key);
return ans;
}
}TypeScript 代码：
function subdomainVisits(ss: string[]): string[] {const map = new Map<string, number>()
for (const s of ss) {
let n = s.length, idx = 0
while (idx < n && s[idx] != ' ') idx++
const cnt = Number(s.substring(0, idx))
const start = idx + 1; idx = n - 1
while (idx >= start) {while (idx >= start && s[idx] != '.') idx--
const cur = s.substring(idx + 1)
if (!map.has(cur)) map.set(cur, 0)
map.set(cur, map.get(cur) + cnt)
idx--
}
}
const ans = new Array<string>()
for (const key of map.keys()) ans.push(map.get(key) + " " + key)
return ans
};Python 代码：
class Solution:
def subdomainVisits(self, ss: List[str]) -> List[str]:
mapping = defaultdict(int)
for s in ss:
n, idx = len(s), 0
while idx < n and s[idx] != ' ':
idx += 1
cnt = int(s[:idx])
start, idx = idx + 1, n - 1
while idx >= start:
while idx >= start and s[idx] != '.':
idx -= 1
mapping[s[idx + 1:]] += cnt
idx -= 1
return [f'{v} {k}' for k, v in mapping.items()]- 工夫复杂度：$O(\sum_{i = 0}^{n – 1}len(ss[i]))$
- 空间复杂度：$O(\sum_{i = 0}^{n – 1}len(ss[i]))$
最初
这是咱们「刷穿 LeetCode」系列文章的第 No.811 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。
在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou…。
在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉
本文由 mdnice 多平台公布