← 返回完整题库
JavaScript困难

请实现一个 LRU 缓存

参考答案

需求:容量上限,get 命中刷新为最新,put 超容量淘汰最久未用。要求 O(1)。

class LRU {
  constructor(cap) { this.cap = cap; this.map = new Map(); }
  get(k) {
    if (!this.map.has(k)) return -1;
    const v = this.map.get(k);
    this.map.delete(k); this.map.set(k, v);   // 刷新到末尾
    return v;
  }
  put(k, v) {
    if (this.map.has(k)) this.map.delete(k);
    this.map.set(k, v);
    if (this.map.size > this.cap) {
      this.map.delete(this.map.keys().next().value); // 淘汰最旧
    }
  }
}

原理

Map 保证插入顺序;delete + set 把键移到末尾(最近使用),首个键即最久未使用。

若手写哈希表 + 双向链表:get 时把节点移到头部,put 超限删尾节点,同样 O(1)。

本题来自 计算机知识面试题库,共 921 道题。