Algorithms first

LRU 缓存 · 交互式算法学习

设计 O(1) get/put 的最近最少使用缓存。

#146 · 链表

LRU 缓存

LRU Cache

测试用例capacity = 2; put(1,1), put(2,2), get(1), put(3,3)

栈 / 队列 / 堆3 个关键状态

进度 1 / 3速度

步骤 1哈希表定位 1、2，链表记录顺序。1↔2

队首

1:1

2:2

get 1

3:3

队尾

哈希表 + 双向链表

时间 所有操作 O(1)空间 O(capacity)

哈希表定位节点；双向链表 O(1) 移动、插入和淘汰尾部。

1class LRUCache {2  constructor(c) {3    this.c = c;4    this.m = new Map()5  }6  get(k) {7    if (!this.m.has(k)) return -1;8    const v = this.m.get(k);9    this.m.delete(k);10    this.m.set(k, v);11    return v12  }13  put(k, v) {14    this.m.delete(k);15    this.m.set(k, v);16    if (this.m.size > this.c) this.m.delete(this.m.keys().next().value)17  }18}

多语言参考

Java · C++ · Go

来源 · CC BY-SA 4.0 ↗

这是一组同题正确实现，独立于上方当前动画方法；不同语言可能采用另一种正确策略。

1class Node {2    int key, val;3    Node prev, next;4 5    Node() {6    }7 8    Node(int key, int val) {9        this.key = key;10        this.val = val;11    }12}13 14class LRUCache {15    private int size;16    private int capacity;17    private Node head = new Node();18    private Node tail = new Node();19    private Map<Integer, Node> cache = new HashMap<>();20 21    public LRUCache(int capacity) {22        this.capacity = capacity;23        head.next = tail;24        tail.prev = head;25    }26 27    public int get(int key) {28        if (!cache.containsKey(key)) {29            return -1;30        }31        Node node = cache.get(key);32        removeNode(node);33        addToHead(node);34        return node.val;35    }36 37    public void put(int key, int value) {38        if (cache.containsKey(key)) {39            Node node = cache.get(key);40            removeNode(node);41            node.val = value;42            addToHead(node);43        } else {44            Node node = new Node(key, value);45            cache.put(key, node);46            addToHead(node);47            if (++size > capacity) {48                node = tail.prev;49                cache.remove(node.key);50                removeNode(node);51                --size;52            }53        }54    }55 56    private void removeNode(Node node) {57        node.prev.next = node.next;58        node.next.prev = node.prev;59    }60 61    private void addToHead(Node node) {62        node.next = head.next;63        node.prev = head;64        head.next = node;65        node.next.prev = node;66    }67}68 69/**70 * Your LRUCache object will be instantiated and called as such:71 * LRUCache obj = new LRUCache(capacity);72 * int param_1 = obj.get(key);73 * obj.put(key,value);74 */

交互式算法学习

从执行步骤真正理解 LeetCode 经典 150

本站整理 150 道高频算法面试题和 302 种解法。动画方法同步展示 JavaScript 与 Python；每题另提供 Java、C++ 与 Go 同题参考实现。

多形态可视化数组、矩阵、DP 表、递归树、树图、链表、栈队列堆、区间和状态机按解法选择。

动画与代码同步当前状态、步骤说明、变量和代码高亮保持一一对应，可逐步播放和回退。

适合面试复习每种方案都给出思路、时间复杂度、空间复杂度、测试用例和 LeetCode 中文原题入口。

AlgoViz Lab

LRU 缓存 · 解法对比

AlgoViz Lab2026-07-112026-07-12

设计 O(1) get/put 的最近最少使用缓存。

测试用例: capacity = 2; put(1,1), put(2,2), get(1), put(3,3)
题目分类: 链表
解法对比: 2

方案 1

数组维护使用顺序

数组按新旧顺序存键；访问时线性定位并移动到末尾。

时间: get/put O(n)
空间: O(capacity)

方案 2

哈希表 + 双向链表

哈希表定位节点；双向链表 O(1) 移动、插入和淘汰尾部。

时间: 所有操作 O(1)
空间: O(capacity)