【刷题日记】811. 子域名访问计数

本次刷题日记的第 63 篇，力扣题为：811. 子域名访问计数，中等

一、题目描述：

子域名的访问计数，有啥特别的呢，何为子域名

二、这道题考察了什么思想？你的思路是什么？

题目虽然描述有点多，我们提炼一下题目给出了哪些重要信息：

• 题目中给出了一个字符串数组，数组中的元素字符串结构是这样的 "数字 域名"

• 其中域名中包含多个 . ，根据 . 的不同来分辨不同级别的域名
• 其中数字表示访问这个域名的次数 num，若域名是 a.b.c 那么，实际上是问了 num 次的 a.b.c , num 次的 b.c ，num 次的 c

• 题目要我们输出和输入数组结构类似的结果数组，包含实际上每一个域名的访问次数

分析

这么看题目给出的重要信息，我们知道，第一时间咱们肯定是需要做切割字符串的操作的，不仅要切割 空格 还需要切割 逗号

最重要的事情那就是将上述分割的结果进行计数了

仔细审题，题目是要求我们将涉及到的子域名，父域名，访问的次数全部计数，且输出结果，那么咱们剩下的其实就是根据不同的域名进行累加即可

那么现在问题来了，如何去存储这些切割后的字符串，且如何累加呢？

刷过题的朋友，对数据结构稍微了解一点的朋友也清楚，咱们可以使用 hash 表来进行处理，hash 表的 key 是不重复的，咱们可以将具体的计数放到 hash 表的值上面

对应到 golang 中，咱们就可以使用 map 来进行实现就可以了，例如题目中给出的例子

9001  ``discuss.leetcode.com

具体的解法就是：

• 定义一个 hash 表
• 遍历题目中给出的数组，处理每一个字符串的时候，拿到具体的 数组， 和具体的域名
• 将域名作为 key ，数值累加到 hash 表中
• 最后遍历 hash 表，按照题目要求的方式输出即可

三、编码

根据上述逻辑和分析，我们就可以翻译成如下代码

• 此处咱们需要注意，创建的 hash 表是 string 对应 int 的类型
• 另外咱们的值是需要累加的

编码如下：

func subdomainVisits(cpdomains []string) []string {
    help := make(map[string]int, 0)
    for _, v := range cpdomains {
        splits := strings.Split(v, " ")
        num, _ := strconv.Atoi(splits[0])
        for {
            help[splits[1]] += num
            // 找到当前域名中的第一个 .
            dotIndex := strings.Index(splits[1], ".")
            // 如果找不到，说明咱们已经是切割到 com 了，即顶级域名
            if dotIndex< 0 {
                break
            }
            // 切割一级域名
            splits[1] = splits[1][dotIndex+1:]
        }
    }
    res := make([]string, 0, len(help))
    for key, v := range help {
        res = append(res, fmt.Sprintf("%d %s", v, key))
    }
    return res
}

四、总结：

这么看来时间复杂度是多少呢？

别看我们这种实现方式是有 2 个循环做嵌套的就无脑的认为时间复杂度是 O(n^2) ，实际上我们还需要看每个循环的次数，外层的循环是 n ，可是内层的循环是一个常熟级别的循环，因为一个域名切割的次数是常数级别的，因此咱们的时间复杂度是 O(n)

空间复杂度是多少呢？

咱们的实现方式引入了一个 hash 表，空间消耗是 O(n) 的级别

原题地址：811. 子域名访问计数

今天就到这里，学习所得，若有偏差，还请斧正

欢迎点赞，关注，收藏

朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力

好了，本次就到这里

技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。

我是阿兵云原生，欢迎点赞关注收藏，下次见~