子域名访问计数
难度:
标签:
题目描述
代码结果
运行时间: 27 ms, 内存: 15.9 MB
/*
* 思路:
* 1. 使用流式处理遍历输入数组中的每个计数配对域名。
* 2. 将计数和域名分开,计数是整数部分,域名是字符串部分。
* 3. 将域名按点分隔成多个子域名,每个子域名累加计数。
* 4. 使用一个哈希映射来记录每个子域名的总访问次数。
* 5. 最后将结果转换为要求的格式。
*/
import java.util.*;
import java.util.stream.*;
public class Solution {
public List<String> subdomainVisits(String[] cpdomains) {
return Arrays.stream(cpdomains)
.map(cpdomain -> cpdomain.split(" "))
.flatMap(parts -> {
int count = Integer.parseInt(parts[0]);
String[] subdomains = parts[1].split("\\.");
return IntStream.range(0, subdomains.length)
.mapToObj(i -> new AbstractMap.SimpleEntry<>(
String.join(".", Arrays.copyOfRange(subdomains, i, subdomains.length)), count));
})
.collect(Collectors.toMap(
Map.Entry::getKey,
Map.Entry::getValue,
Integer::sum
))
.entrySet()
.stream()
.map(entry -> entry.getValue() + " " + entry.getKey())
.collect(Collectors.toList());
}
}
解释
方法:
题解的核心思路是使用哈希表(字典)来记录每个域名及其子域名的访问次数。对于每个输入的域名配对,首先将次数和域名分离,然后添加该域名的访问次数到哈希表。接着通过循环移除域名的最左部分(直到没有'.'为止),不断更新哈希表中对应子域名的访问次数。最后,将哈希表中的数据格式化为所需的输出格式。
时间复杂度:
O(nk)
空间复杂度:
O(m)
代码细节讲解
🦆
在处理子域名时,为什么选择从左到右逐步移除最左部分的域名来更新哈希表,而不是其他分割方式?
▷🦆
如何确保在分割域名时不会遗漏或错误处理某些复杂的域名结构?
▷🦆
给定的解决方案中,如何处理可能出现的整数溢出问题,特别是当访问次数非常大时?
▷🦆
在最后格式化输出结果时,为什么选择将域名和访问次数反转输出而不是维持输入格式?
▷