leetcode
leetcode 701 ~ 750
子域名访问计数

子域名访问计数

难度:

标签:

题目描述

代码结果

运行时间: 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)

代码细节讲解

🦆
在处理子域名时,为什么选择从左到右逐步移除最左部分的域名来更新哈希表,而不是其他分割方式?
从左到右逐步移除最左部分的域名来更新哈希表的方法可以确保所有可能的子域名都被考虑在内。这种方法通过从整个域名开始,逐步通过移除最前面的部分来获取所有下级域名,可以保证从最具体的域名到最广泛的域名的顺序。这样可以有效地使用循环来捕获和计数所有子域名的访问次数,而不需要额外的复杂逻辑或递归处理。
🦆
如何确保在分割域名时不会遗漏或错误处理某些复杂的域名结构?
在分割域名时,使用标准的字符串操作如索引查找'.'来判断分割点,这是根据域名规范来进行的。为了确保不遗漏或错误处理,程序中应该严格按照域名结构规则来操作,考虑到所有域名都是由多个用点('.')分隔的部分组成。此外,进行任何字符串操作前,应检查字符串的有效性,如非空检查,以及确认有分隔符存在。这些措施可以帮助避免处理错误或非标准的域名结构。
🦆
给定的解决方案中,如何处理可能出现的整数溢出问题,特别是当访问次数非常大时?
在Python中,整数类型是动态的,可以根据需要自动扩展到较大的数值,因此通常不必担心常规整数运算中的溢出问题。然而,对于非常大的数据集或在其他编程语言中,应考虑使用大数处理库或数据类型,如Java中的BigInteger。此外,还可以通过适时的数据聚合和压缩,以及在处理前对数据进行分片或批处理来降低内存压力和避免运算时的潜在溢出。
🦆
在最后格式化输出结果时,为什么选择将域名和访问次数反转输出而不是维持输入格式?
在最后格式化输出结果时,将域名和访问次数反转输出是为了符合题目要求的输出格式,即'访问次数 域名'的形式。这种格式更直观地反映了每个域名的访问量,同时也方便了结果的阅读和后续的数据处理,如排序或进一步的分析。这是一种常见的数据表示方式,特别是在需要突出显示数量或统计数据时。

相关问题