题目

标题和出处

标题：子域名访问计数

出处：811. 子域名访问计数

难度

4 级

题目描述

要求

网站域名 "discuss.leetcode.com"\texttt{"discuss.leetcode.com"}"discuss.leetcode.com" 由多个子域名组成。顶级域名为 "com"\texttt{"com"}"com"，二级域名为 "leetcode.com"\texttt{"leetcode.com"}"leetcode.com"，最低一级为 "discuss.leetcode.com"\texttt{"discuss.leetcode.com"}"discuss.leetcode.com"。当访问域名 "discuss.leetcode.com"\texttt{"discuss.leetcode.com"}"discuss.leetcode.com" 时，同时也会隐式访问其父域名 "leetcode.com"\texttt{"leetcode.com"}"leetcode.com" 以及 "com"\texttt{"com"}"com"。

计数配对域名是遵循 "repd1.d2.d3"\texttt{"rep d1.d2.d3"}"rep d1.d2.d3" 或 "repd1.d2"\texttt{"rep d1.d2"}"rep d1.d2" 格式的一个域名表示，其中 rep\texttt{rep}rep 表示访问域名的次数，d1.d2.d3\texttt{d1.d2.d3}d1.d2.d3 为域名本身。

例如，"9001discuss.leetcode.com"\texttt{"9001 discuss.leetcode.com"}"9001 discuss.leetcode.com" 就是一个计数配对域名，表示 discuss.leetcode.com\texttt{discuss.leetcode.com}discuss.leetcode.com 被访问了 9001\texttt{9001}9001 次。

给你一个计数配对域名组成的数组 cpdomains\texttt{cpdomains}cpdomains，解析得到输入中每个子域名对应的计数配对域名，并以数组形式返回。可以按任意顺序返回答案。

示例

示例 1：

输入：cpdomains=["9001discuss.leetcode.com"]\texttt{cpdomains = ["9001 discuss.leetcode.com"]}cpdomains = ["9001 discuss.leetcode.com"]
输出：["9001leetcode.com","9001discuss.leetcode.com","9001com"]\texttt{["9001 leetcode.com","9001 discuss.leetcode.com","9001 com"]}["9001 leetcode.com","9001 discuss.leetcode.com","9001 com"]
解释：例子中仅包含一个网站域名："discuss.leetcode.com"\texttt{"discuss.leetcode.com"}"discuss.leetcode.com"。
按照前文描述，子域名 "leetcode.com"\texttt{"leetcode.com"}"leetcode.com" 和 "com"\texttt{"com"}"com" 都会被访问，所以它们都被访问了 9001\texttt{9001}9001 次。

示例 2：

输入：cpdomains=["900google.mail.com","50yahoo.com","1intel.mail.com","5wiki.org"]\texttt{cpdomains = ["900 google.mail.com", "50 yahoo.com", "1 intel.mail.com", "5 wiki.org"]}cpdomains = ["900 google.mail.com", "50 yahoo.com", "1 intel.mail.com", "5 wiki.org"]
输出：["901mail.com","50yahoo.com","900google.mail.com","5wiki.org","5org","1intel.mail.com","951com"]\texttt{["901 mail.com","50 yahoo.com","900 google.mail.com","5 wiki.org","5 org","1 intel.mail.com","951 com"]}["901 mail.com","50 yahoo.com","900 google.mail.com","5 wiki.org","5 org","1 intel.mail.com","951 com"]
解释：按照前文描述，会访问 "google.mail.com"\texttt{"google.mail.com"}"google.mail.com" 900\texttt{900}900 次，"yahoo.com"\texttt{"yahoo.com"}"yahoo.com" 50\texttt{50}50 次，"intel.mail.com"\texttt{"intel.mail.com"}"intel.mail.com" 1\texttt{1}1 次，"wiki.org"\texttt{"wiki.org"}"wiki.org" 5\texttt{5}5 次。
而对于父域名，会访问 "mail.com"\texttt{"mail.com"}"mail.com" 900+1=901\texttt{900 + 1 = 901}900 + 1 = 901 次，"com"\texttt{"com"}"com" 900+50+1=951\texttt{900 + 50 + 1 = 951}900 + 50 + 1 = 951 次，和 "org"\texttt{"org"}"org" 5\texttt{5}5 次。

数据范围

1≤cpdomain.length≤100\texttt{1} \le \texttt{cpdomain.length} \le \texttt{100}1≤cpdomain.length≤100
1≤cpdomain[i].length≤100\texttt{1} \le \texttt{cpdomain[i].length} \le \texttt{100}1≤cpdomain[i].length≤100
cpdomain[i]\texttt{cpdomain[i]}cpdomain[i] 会遵循 "repid1i.d2i.d3i"\texttt{"rep}_\texttt{i}\texttt{ d1}_\texttt{i}\texttt{.d2}_\texttt{i}\texttt{.d3}_\texttt{i}\texttt{"}"repi d1i.d2i.d3i" 或 "repid1i.d2i"\texttt{"rep}_\texttt{i}\texttt{ d1}_\texttt{i}\texttt{.d2}_\texttt{i}\texttt{"}"repi d1i.d2i" 格式
repi\texttt{rep}_\texttt{i}repi 是范围 [1,104]\texttt{[1, 10}^\texttt{4}\texttt{]}[1, 104] 内的一个整数
d1i\texttt{d1}_\texttt{i}d1i、d2i\texttt{d2}_\texttt{i}d2i 和 d3i\texttt{d3}_\texttt{i}d3i 由小写英语字母组成

解法

思路和算法

为了得到每个子域名对应的计数配对域名，需要记录每个子域名的访问次数，可以使用哈希表记录。

对于给定数组 cpdomains\textit{cpdomains}cpdomains 中的每个元素，都可以得到访问次数和域名，然后得到域名对应的全部子域名，并将该域名的访问次数加到每个子域名的总访问次数。

由于域名的各部分之间用点号分隔，因此可以定位到每个点号的下标，并获得每个子域名，然后更新每个子域名的总访问次数。

在遍历完数组 cpdomains\textit{cpdomains}cpdomains 之后，哈希表中记录的即为所有子域名的访问次数。再遍历哈希表，对于每个子域名，根据访问次数和子域名得到计数配对域名，并添加到结果列表。

代码

class Solution {public List subdomainVisits(String[] cpdomains) {Map map = new HashMap();for (String cpdomain : cpdomains) {int spaceIndex = cpdomain.indexOf(' ');int count = Integer.parseInt(cpdomain.substring(0, spaceIndex));String domain = cpdomain.substring(spaceIndex + 1);int dotIndex = -1;do {String subdomain = domain.substring(dotIndex + 1);map.put(subdomain, map.getOrDefault(subdomain, 0) + count);dotIndex = domain.indexOf('.', dotIndex + 1);} while (dotIndex >= 0);}List visits = new ArrayList();Set> entries = map.entrySet();for (Map.Entry entry : entries) {String subdomain = entry.getKey();int count = entry.getValue();String subdomainCount = count + " " + subdomain;visits.add(subdomainCount);}return visits;}
}

复杂度分析

时间复杂度：O(L)O(L)O(L)，其中 LLL 是数组 cpdomains\textit{cpdomains}cpdomains 中的所有字符串长度之和。
需要遍历数组 cpdomains\textit{cpdomains}cpdomains 中的每个字符串计算每个子域名的总访问次数，由于每个域名都需要遍历一次，因此需要 O(L)O(L)O(L) 的时间。
遍历哈希表时，由于每个域名最多有三个部分，因此遍历哈希表需要 O(L)O(L)O(L) 的时间。
因此总时间复杂度是 O(L)O(L)O(L)。
空间复杂度：O(L)O(L)O(L)，其中 LLL 是数组 cpdomains\textit{cpdomains}cpdomains 中的所有字符串长度之和。空间复杂度主要取决于哈希表，需要使用哈希表记录每个子域名的总访问次数，由于每个域名最多有三个部分，因此哈希表的空间复杂度是 O(L)O(L)O(L)。注意返回值不计入空间复杂度。

词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：Mybatis笔记一

下一篇：Linux -- 磁盘存储管理分区工具 parted