宫水三叶的刷题日记

V1

2022/10/05阅读:16主题:前端之巅同款

811. 子域名访问计数 : 简单哈希表运用题

题目描述

这是 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 次。

提示:

  • cpdomain[i] 会遵循 "repi d1i.d2i.d3i""repi d1i.d2i" 格式
  • repi 是范围 内的一个整数
  • 由小写英文字母组成

哈希表

为了方便,我们令 cpdomainsss

根据题意进行模拟:使用哈希表记录每个域名的总访问次数,从前往后处理所有的 。在处理某个 时(记长度为 ,使用指针 idx 代指扫描到的游标位置),先通过指针扫描找到访问数字部分 cnt = ss[i][0:idx],然后「从后往前」处理 部分,按照域名层级「从小到大」的顺序进行截取,并累加访问次数 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<stringnumber>()
    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()]
  • 时间复杂度:
  • 空间复杂度:

最后

这是我们「刷穿 LeetCode」系列文章的第 No.811 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。

在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉

分类:

后端

标签:

后端

作者介绍

宫水三叶的刷题日记
V1