677.键值映射.md

677.键值映射

/*
 * @lc app=leetcode.cn id=677 lang=typescript
 *
 * [677] 键值映射
 */

// @lc code=start
class MapSum {
  constructor() {}
  insert(key: string, val: number): void {}

  sum(prefix: string): number {}
}

/**
 * Your MapSum object will be instantiated and called as such:
 * var obj = new MapSum()
 * obj.insert(key,val)
 * var param_2 = obj.sum(prefix)
 */
// @lc code=end

解法 1: 字典树

利用字典树保存数据

在插入时累加前缀和,这样可以用 O(1) 的时间取到前缀和

interface TrieNode {
  value: number
  children: {
    [key: string]: TrieNode
  }
}

class MapSum {
  _trie: TrieNode = { value: 0, children: {} }
  _map: { [key: string]: number } = {}
  constructor() {}

  insert(key: string, val: number): void {
    const dif = val - (this._map[key] ?? 0)
    this._map[key] = val
    let node = this._trie

    for (const char of key) {
      if (!node.children[char]) node.children[char] = { value: 0, children: {} }
      node = node.children[char]
      node.value = node.value + dif
    }
  }

  sum(prefix: string): number {
    let node = this._trie
    for (const char of prefix) {
      node = node.children[char]
      if (!node) return 0
    }
    return node.value
  }
}

Case

test.each([
  {
    input: {
      operations: ['MapSum', 'insert', 'sum', 'insert', 'sum'],
      param: [[], ['apple', 3], ['ap'], ['app', 2], ['ap']],
    },
    output: [null, null, 3, null, 5],
  },
])('input: param = $input.param', ({ input: { operations, param }, output }) => {
  const mapSum = new MapSum()
  const res: (null | number)[] = [null]
  for (let i = 1; i < operations.length; i++) {
    const operation = operations[i]
    if (operation === 'insert') {
      const [key, val] = param[i] as [string, number]
      mapSum[operation](key, val)
      res.push(null)
    } else if (operation === 'sum') {
      res.push(mapSum[operation](param[i][0] as string))
    }
  }

  expect(res).toEqual(output)
})