LeetCode146.LRU缓存

更新: 5/15/2026 字数: 0 字 时长: 0 分钟

题目链接：LeetCode146. LRU 缓存

让我们设计一个LRUCache类，包括构造函数+get()+put()方法。

核心思路就是用双向链表+Hash表。Hash表用来存key-value键值对，双向链表我们可以自己写一个类来模拟，主要就是有next和prev两个指针分别指向前面的和后面的，然后定义head和tail两个指针用来保存头尾，头部是最近使用的关键字，尾部则是最久没使用的关键字，查询时判断hash表有没有，如果有则返回并放到头部，put方法比较复杂，需要判断是否有无，详细解析看代码:

// 自定义的双向链表
struct DLinkNode {
    int key;
    int value;
    // 前一个节点
    DLinkNode* prev;
    // 后一个节点
    DLinkNode* next;
    // 两个构造方法
    DLinkNode(): key(0), value(0), prev(nullptr) ,next(nullptr) {}
    DLinkNode(int _key, int _value): key(_key), value(_value), prev(nullptr), next(nullptr) {}
};

class LRUCache {
    // 存关键字的hashMap,注意这里的值是一个节点
    unordered_map<int, DLinkNode*> cache;
    // 头指针(head -> next为第一个节点)
    DLinkNode* head;
    // 尾指针(tail -> prev为最后一个节点)
    DLinkNode* tail;
    // 当前容量大小
    int size;
    // 最大容量
    int capacity;
public:
    LRUCache(int capacity) {
        // 初始化
        head = new DLinkNode();
        tail = new DLinkNode();
        head -> next = tail;
        tail -> prev = head;
        this -> capacity = capacity;
        size = 0;
    }
    
    int get(int key) {
        // 如果没有就返回-1
        if(cache.count(key) == 0) return -1;
        DLinkNode* tmp = cache[key];
        // 移动到头节点(因为被使用过了)
        moveToHead(tmp);
        return tmp -> value;
    }
    
    void put(int key, int value) {
        // 如果有这个节点则返回并移动到头节点
        if(cache.count(key) != 0) {
            DLinkNode* tmp = cache[key];
            tmp -> value = value;
            // 移动到头节点(因为被使用过了)
            moveToHead(tmp);
            return;
        }
        // 下面是没有这个节点的情况
        // 需要先创建一个节点
        DLinkNode* node = new DLinkNode(key, value);
        // 加入hashMap里面
        cache[key] = node;
        // 这里是把这个节点放到头节点，注意需要与移动区分开
        node -> prev = head;
        node -> next = head -> next;
        head -> next -> prev = node;
        head -> next = node;
        // size++
        size++;
        // 如果超出最大容量，则需要移除最久未使用的也就是最后一个节点
        if(size > capacity) {
            // 取出最后一个节点
            DLinkNode* removed = tail -> prev;
            // 从hashMap中移除
            cache.erase(removed -> key);
            // 把removed的上一个结点作为最后一个节点
            removed -> prev -> next = tail;
            // 把尾节点的前一个设置为目前的最后一个节点(双向都要连接)
            tail -> prev = removed -> prev;
            // size--
            size--;
        } 
    }
    // 将一个节点移到第一个，思路就是先断开再连接
    void moveToHead(DLinkNode* node) {
        // 断开这个节点，把前后相连
        node -> prev -> next = node -> next;
        node -> next -> prev = node -> prev;
        // 把这个节点放到头部
        node -> prev = head;
        node -> next = head -> next;
        head -> next -> prev = node;
        head -> next = node;
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

时间复杂度：put和get都是$O(1)$。

空间复杂度:$O(capacity)$，因为哈希表和双向链表最多存储 capacity+1 个元素。