🔗 LRU 缓存

题目来源：146. LRU 缓存 – 力扣（LeetCode）

📌 题目要求

设计一个满足 LRU（Least Recently Used，最近最少使用） 策略的缓存结构，支持以下操作：

• LRUCache(int capacity)：以正整数 capacity 初始化缓存
• int get(int key)：若 key 存在，返回对应值，并将其标记为“最近使用”；否则返回 -1
• void put(int key, int value)：
  • 若 key 已存在，更新其值并标记为“最近使用”
  • 若 key 不存在，插入新键值对
  • 若插入后超出容量，淘汰最久未使用的 key

✅ 核心约束：get 和 put 必须以 O(1) 平均时间复杂度 运行。

✅ 示例说明

输入：
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1,1], [2,2], [1], [3,3], [2], [4,4], [1], [3], [4]]

输出：
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释：容量为 2，当插入第 3 个元素时，淘汰最久未使用的（2），后续同理。

💡 解法：哈希表 + 虚拟头尾节点的双向链表

class LRUCache {
    private class Node {
        int key, value;
        Node prev, next;
        Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    private int capacity;
    private Node dummy = new Node(-1, -1);
    private Map<Integer, Node> map = new HashMap<>();

    public LRUCache(int capacity) {
        this.capacity = capacity;
        dummy.next = dummy;
        dummy.prev = dummy;
    }

    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        Node node = map.get(key);
        remove(node);
        addToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            node.value = value;
            remove(node);
            addToHead(node);
        } else {
            if (map.size() == capacity) {
                Node tail = dummy.prev;
                remove(tail);
                map.remove(tail.key);
            }
            Node newNode = new Node(key, value);
            addToHead(newNode);
            map.put(key, newNode);
        }
    }

    private void remove(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void addToHead(Node node) {
        node.next = dummy.next;
        node.prev = dummy;
        dummy.next.prev = node;
        dummy.next = node;
    }
}

📊 复杂度分析

• 时间复杂度：O(1)
  • 哈希表支持 O(1) 查找
  • 双向链表支持 O(1) 删除与头插
• 空间复杂度：O(capacity)
  • 最多存储 capacity 个节点

🧩 设计原理

LRU 的核心是 快速定位 + 快速调整使用顺序，需同时满足：

1. 快速查找 → 使用 HashMap<Integer, Node>，key 映射到链表节点
2. 维护使用顺序 → 使用双向链表：
   • 链表头部：最近使用
   • 链表尾部：最久未使用
3. 快速删除尾节点 & 插入头节点 → 双向链表天然支持 O(1) 操作

为简化边界处理，引入虚拟头节点 dummy，构成环状结构（dummy.next 为真实头，dummy.prev 为真实尾），避免空指针判断。

操作逻辑：

• get(key)：
  • 不存在 → 返回 -1
  • 存在 → 从链表中移除该节点，重新插入头部，返回值
• put(key, value)：
  • 已存在 → 更新值，移至头部
  • 不存在：
    • 若已满 → 删除尾节点（dummy.prev），从 map 中移除
    • 创建新节点，插入头部，加入 map