5. LRU 缓存 %26%26 字典树 （Trie）

LRU Cache

// LRUCache 构造函数，参数为容量
var LRUCache = function(capacity) {
  this.capacity = capacity
  this.map = new Map()
};
// get: 如果 key 存在，则覆盖这个 key 的值，否则返回 -1
LRUCache.prototype.get = function(key) {
  if (this.map.has(key)) {
    const value = this.map.get(key)
    this.map.delete(key)
    this.map.set(key, value)
    return value
  }
  return -1
};
// put：需要判断 key 是否存在，是否超出容量
LRUCache.prototype.put = function(key, value) {
  if (this.map.has(key)) {
    this.map.delete(key)
  } else if (this.map.size === this.capacity) {
    // 如果容量满了，删除最近添加的 key
    this.map.delete(this.map.keys().next().value)
  }
  this.map.set(key, value)
};

字典树、前缀树、Trie

class Trie {
  constructor() {
    this.root = {};
  }
  insert(word) {
    let node = this.root;
    for (let c of word) {
      if (node[c] == null) node[c] = {};
      node = node[c];
    }
    node.isWord = true;
  }
  traverse(word) {
    let node = this.root;
    for (let c of word) {
      node = node[c];
      if (node == null) return null;
    }
    return node;
  }
  search(word) {
    const node = this.traverse(word);
    return node != null && node.isWord === true;
  }
  startsWith(prefix) {
    return this.traverse(prefix) != null;
  }
}