TNotes.leetcode

Appearance

⏰0811. 子域名访问计数【中等】

0811. 子域名访问计数【中等】 ​

1. 📝 题目描述 ​

网站域名 "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：

txt
输入：cpdomains = ["9001 discuss.leetcode.com"]
输出：["9001 leetcode.com","9001 discuss.leetcode.com","9001 com"]
解释：例子中仅包含一个网站域名："discuss.leetcode.com"。
按照前文描述，子域名 "leetcode.com" 和 "com" 都会被访问，所以它们都被访问了 9001 次。

示例 2：

txt
输入：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] 内的一个整数
  • d1i、d2i 和 d3i 由小写英文字母组成

2. 🎯 s.1 - 哈希表 ​

c
typedef struct Entry { char domain[256]; int count; struct Entry* next; } Entry;
#define HASH_SIZE 1009

unsigned hashStr(char* s) {
    unsigned h = 0;
    while (*s) h = h * 31 + *s++;
    return h % HASH_SIZE;
}

void addCount(Entry** table, char* domain, int count) {
    unsigned h = hashStr(domain);
    for (Entry* e = table[h]; e; e = e->next) {
        if (strcmp(e->domain, domain) == 0) { e->count += count; return; }
    }
    Entry* e = (Entry*)malloc(sizeof(Entry));
    strcpy(e->domain, domain);
    e->count = count;
    e->next = table[h];
    table[h] = e;
}

char** subdomainVisits(char** cpdomains, int cpdomainsSize, int* returnSize) {
    Entry* table[HASH_SIZE];
    memset(table, 0, sizeof(table));
    for (int i = 0; i < cpdomainsSize; i++) {
        int cnt; char domain[256];
        sscanf(cpdomains[i], "%d %s", &cnt, domain);
        int n = strlen(domain);
        for (int j = 0; j < n; j++) {
            if (j == 0 || domain[j - 1] == '.') addCount(table, domain + j, cnt);
        }
    }
    char** res = (char**)malloc(sizeof(char*) * 10000);
    *returnSize = 0;
    for (int i = 0; i < HASH_SIZE; i++) {
        for (Entry* e = table[i]; e; e = e->next) {
            res[*returnSize] = (char*)malloc(300);
            sprintf(res[*returnSize], "%d %s", e->count, e->domain);
            (*returnSize)++;
        }
    }
    return res;
}
js
/**
 * @param {string[]} cpdomains
 * @return {string[]}
 */
var subdomainVisits = function (cpdomains) {
  const map = new Map()
  for (const cp of cpdomains) {
    const [cnt, domain] = cp.split(' ')
    const count = Number(cnt)
    const parts = domain.split('.')
    for (let i = 0; i < parts.length; i++) {
      const sub = parts.slice(i).join('.')
      map.set(sub, (map.get(sub) || 0) + count)
    }
  }
  const res = []
  for (const [domain, count] of map) res.push(`${count} ${domain}`)
  return res
}
py
class Solution:
    def subdomainVisits(self, cpdomains: List[str]) -> List[str]:
        from collections import Counter
        cnt = Counter()
        for cp in cpdomains:
            count, domain = cp.split()
            count = int(count)
            parts = domain.split('.')
            for i in range(len(parts)):
                cnt['.'.join(parts[i:])] += count
        return [f'{c} {d}' for d, c in cnt.items()]
  • 时间复杂度：O(n×m)，其中 n 是域名数，m 是子域名平均层数
  • 空间复杂度：O(n×m)

算法思路：

  • 对每个域名，拆分出所有子域名并累加访问次数到哈希表中