面试题10.10.数字流的秩

链接：面试题10.10.数字流的秩
难度：Medium
标签：设计、树状数组、二分查找、数据流
简介：实现一个 MapSum 类。

题解 1 - typescript

• 编辑时间：2021-11-14
• 执行用时：80ms
• 内存消耗：39.8MB
• 编程语言：typescript
• 解法介绍：trie。

const getIdx = (ch: string) => ch.codePointAt(0)! - 'a'.codePointAt(0)!;
class TrieNode {
  data = 0;
  end = false;
  children: TrieNode[] = [];
  constructor(public val: string) {}
  sum() {
    let sum = this.data;
    for (const child of this.children) {
      if (child) sum += child.sum();
    }
    return sum;
  }
}
class Trie {
  root = new TrieNode('');
  insert(word: string, data: number): void {
    let node = this.root;
    for (const ch of word) {
      const idx = getIdx(ch);
      if (!node.children[idx]) node.children[idx] = new TrieNode(ch);
      node = node.children[idx];
    }
    node.data = data;
    node.end = true;
  }
  findNode(word: string): TrieNode | null {
    let node = this.root;
    for (const ch of word) {
      const idx = getIdx(ch);
      if (!node.children[idx]) return null;
      node = node.children[idx];
    }
    return node;
  }
  search(word: string): boolean {
    return !!this.findNode(word)?.end;
  }
  startsWith(prefix: string): boolean {
    return !!this.findNode(prefix);
  }
}
class MapSum {
  trie = new Trie();
  insert(key: string, val: number): void {
    this.trie.insert(key, val);
  }
  sum(prefix: string): number {
    return this.trie.findNode(prefix)?.sum() ?? 0;
  }
}