关于后端:811-子域名访问计数-简单哈希表运用题

34次阅读

共计 2947 个字符,预计需要花费 8 分钟才能阅读完成。

题目形容

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

提醒:

  • $1 <= cpdomain.length <= 100$
  • $1 <= cpdomain[i].length <= 100$
  • cpdomain[i] 会遵循 "repi d1i.d2i.d3i""repi d1i.d2i" 格局
  • repi 是范畴 $[1, 10^4]$ 内的一个整数
  • $d1_i$、$d2_i$ 和 $d3_i$ 由小写英文字母组成

哈希表

为了不便,咱们令 cpdomainsss

依据题意进行模仿:应用哈希表记录每个域名的总拜访次数,从前往后解决所有的 $ss[i]$。在解决某个 $ss[i]$ 时(记长度为 $n$,应用指针 idx 代指扫描到的游标位置),先通过指针扫描找到拜访数字局部 cnt = ss[i][0:idx],而后「从后往前」解决 $ss[i]$ 的 $[idx + 1, n – 1]$ 局部,依照域名层级「从小到大」的程序进行截取,并累加拜访次数 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<string, number>()
    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()]
  • 工夫复杂度:$O(\sum_{i = 0}^{n – 1}len(ss[i]))$
  • 空间复杂度:$O(\sum_{i = 0}^{n – 1}len(ss[i]))$

最初

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

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

为了不便各位同学可能电脑上进行调试和提交代码,我建设了相干的仓库:https://github.com/SharingSou…。

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

更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉

本文由 mdnice 多平台公布

正文完
 0