复盘 · LC 146 LRU 缓存

题目

• 题号：LeetCode 146
• 名称：LRU 缓存（LRU Cache）
• 难度：Medium
• 链接：leetcode.cn/problems/lru-cache
• 今日代码：146-LRU缓存/index.js

题意

设计容量固定为 capacity 的缓存，支持：

• get(key)：存在则返回值，并把该键标为最近使用；否则 -1
• put(key, value)：写入/更新；若超出容量，淘汰最久未使用的键

要求 get / put 平均 O(1)。

边界：capacity === 1、反复 get 同一键、put 更新已有键、满后再 put 新键。

涉及算法

标签	一句话
哈希 + 双向链表	Map 查结点；链表头=最近、尾=最久；访问/写入时挪到头，满则删尾
JS Map 有序	利用插入顺序：delete 再 set 等价「移到最新」；超容删 keys().next()

教程对照：设计题，系列里无专篇；哈希手感见 09 · 哈希表进阶，链表改指向见 12。

评价我的解法

我的代码（摘自 146-LRU缓存/index.js，不含本地测例与注释掉的 console.log）：

var LRUCache = function (capacity) {
  this.capacity = capacity;
  this.count = 0;
  this.map = new Map();
  this.head = null;
  this.tail = null;
};

LRUCache.prototype.get = function (key) {
  const obj = this.map.get(key);
  if (obj && obj.value != undefined) {
    const node = obj.node;
    if (node === this.head) {
      return obj.value;
    }
    const pre = node.pre;
    if (pre) {
      pre.next = node.next;
    }
    if (node === this.tail) {
      this.tail = pre;
    }
    node.pre = null;
    node.next = this.head;
    this.head.pre = node;
    this.head = node;
    return obj.value;
  } else {
    return -1;
  }
};

LRUCache.prototype.put = function (key, value) {
  const obj = this.map.get(key);
  if (obj && obj.value != undefined) {
    const node = obj.node;
    if (node === this.head) {
      return;
    }
    node.value = value;
    const pre = obj.node.pre;
    if (pre) {
      pre.next = node.next;
    }
    if (node === this.tail) {
      this.tail = pre;
    }
    node.pre = this.head;
    this.head.next = node;
    this.head = node;
    return;
  }
  this.count++;
  if (!this.head) {
    this.head = {
      key,
      value,
      next: null,
      pre: null,
    };
    this.tail = this.head;
    this.map.set(key, {
      value: value,
      node: this.head,
    });
    return;
  }
  const node = {
    key,
    value,
    next: this.head.next,
    pre: null,
  };
  this.map.set(key, {
    value: value,
    node: node,
  });

  if (this.count > this.capacity) {
    const node = this.tail.pre;
    const tail = this.tail;
    if (!node) {
      if (this.tail) {
        this.tail = null;
        this.map.delete(tail.key);
      }
      return;
    }
    this.map.delete(tail.key);
    node.next = null;
    this.tail = node;
    this.count--;
  }

  node.next = this.head;
  this.head.pre = node;
  this.head = node;
};

文件末尾自评「写不出来，只能通过一部分」——和代码事实一致：方向对（Map + 双向链表），实现未闭环。

• 对在哪：知道要用哈希定位 + 链表维护新旧顺序；get 有「移到头部」的意图。
• 错/糙在哪（导致部分用例挂）：
  1. put 更新且已是 head：直接 return，没改 value。
  2. put 更新挪头：node.pre = this.head; this.head.next = node 把旧头的 next 掐断，链表易断；中间结点拆出时未修 node.next.pre。
  3. capacity === 1 淘汰：tail.pre 为空时 return，新结点没挂上（本地测例正是 capacity 1）。
  4. Map 里 { value, node } 与结点上 value 双份，更新时易不同步；count 与真实长度也容易漂。
• 复杂度目标对，但正确性未达标，谈不上 O(1) 稳定实现。

最佳题解

面试可讲「哈希 + 双向链表」；JS 日常可用 Map 插入序（更短、不易断链）：

/**
 * @param {number} capacity
 */
var LRUCache = function (capacity) {
  this.cap = capacity;
  this.map = new Map();
};

/**
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function (key) {
  if (!this.map.has(key)) return -1;
  const val = this.map.get(key);
  this.map.delete(key);
  this.map.set(key, val);
  return val;
};

/**
 * @param {number} key
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function (key, value) {
  if (this.map.has(key)) this.map.delete(key);
  this.map.set(key, value);
  if (this.map.size > this.cap) {
    const oldest = this.map.keys().next().value;
    this.map.delete(oldest);
  }
};

• 时间 均摊 O(1)，空间 O(capacity)。
• 为何更优：不手撕 pre/next，用语言特性保证「删再插 = 最近」；超容删最先插入仍在的键即最久未用。

若坚持手写双向链表：加 dummy head/tail，封装 remove(node) / addToHead(node)，所有路径只调这两个函数——避免今天这种分支爆炸。

关联题目

题	为何相关
460. LFU 缓存	设计题升级：频次 + 新旧
432. 全 O(1) 的数据结构	哈希 + 链表维护最值
138. 随机链表的复制	哈希存结点映射的另一用法

一句话带走

LRU：先保证「查 O(1) + 挪到最新 + 满删最旧」三条语义；JS 用 Map 有序最快落地，手写链表必须 dummy + 统一拆/挂。