Leetcode 146.LRU 缓存机制

2021-07-03
作者 Ender
4.35K 字
次阅读

题目描述：

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。

实现 LRUCache 类：

LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

进阶：你是否可以在 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]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

提示：

$1 <= capacity <= 3000$
$0 <= key <= 3000$
$0 <= value <= 10^4$
最多调用 $3 * 10^4$ 次 get 和 put

链接：

https://leetcode-cn.com/problems/lru-cache

题目分析

LRU 也即 Least Recently Used，最近最少使用。顾名思义，最近最少使用的结点会从缓存删去，那么怎么判断哪个结点是最近没有被使用到的呢？我们可以维护一个双向链表作为缓存，越靠近头部表示上一次被使用的时间越近，如果一个结点被使用，就将其移动到链表头部（没有则也是添加到头部），而如果缓存区已满，则删除链表末尾的结点。而我们怎么快速找到结点呢？题目说明了每个结点具有不同的关键字，则我们可以使用一个哈希表来存储结点的指针。所以我们采用的是一个双向链表加一个哈希表的数据结构。（PS：为什么要使用双向链表而不是单向链表呢？因为我们需要频繁地从链表中删除结点（包括移动操作和删除操作），使用双向链表才可以在定位后对前后进行连接操作。）
从实现的细节上来说，我们经常操作的是链表的头结点和尾结点，为了避免多次判定链表是否为空（链表为空时添加的新结点既是头结点也是尾结点），我们使用了两个哨兵结点，分别作为伪头部和伪尾部。
各操作的作用已经包含到代码的注释中。

class LRUCache {
    // 双向链表的单个结点，包含 key 和 value 还有指向前后结点的指针
    struct LinkNode{
        int key, value;
        LinkNode *next;
        LinkNode *prev;
        LinkNode():key(0), value(0), next(nullptr), prev(nullptr){}
        LinkNode(int _key, int _value):key(_key), value(_value), next(nullptr), prev(nullptr){}
    };

    unordered_map<int, LinkNode*> cache; // 根据 key 快速定位结点的哈希表
    LinkNode *head, *tail; // 伪头部和伪尾部
    int capacity;   // 缓存的最大容量
    int count;  // 当前缓存的大小

    // 将结点添加到头部
    void addToHead(LinkNode *node){
        node->next = head->next;
        node->next->prev = node;
        head->next = node;
        node->prev = head;
    }

    // 从链表中删除一个结点
    void removeNode(LinkNode *node){
        node->next->prev = node->prev;
        node->prev->next = node->next;
    }

    // 将一个结点移到头部
    void moveToHead(LinkNode *node){
        removeNode(node);
        addToHead(node);
    }

    // 从尾部删除一个结点（返回这个结点用于内存释放）
    LinkNode* removeTail(){
        LinkNode *del = tail->prev;
        removeNode(del);
        return del;
    }
public:
    LRUCache(int capacity) {
        // 初始化缓存容量并且设置好哨兵结点
        this->capacity = capacity;
        this->count = 0;
        head = new LinkNode();
        tail = new LinkNode();
        head->next = tail;
        tail->prev = head;
    }
    
    int get(int key) {
        // 找不到则返回 -1
        if(!cache.count(key)) return -1;

        // 从哈希表中定位结点，将其移到头部
        LinkNode *node = cache[key];
        moveToHead(node);

        // 返回结点值
        return node->value;
    }
    
    void put(int key, int value) {
        // 如果这个 key 不存在于缓存中则需添加
        if(!cache.count(key)){
            LinkNode *newnode = new LinkNode(key, value);
            // 添加到哈希表中和链表中
            cache[key] = newnode;
            addToHead(newnode);
            count++;
            // 添加结点后需要判断缓存是否已经溢出
            if(count > capacity){
                // 从链表和哈希表中删除并释放内存
                LinkNode *del = removeTail();
                cache.erase(del->key);
                delete del;
                count--;
            }
        }
        // 这个 key 已经存在缓存中则需要更新结点值并移到头部
        else{
            LinkNode *node = cache[key];
            node->value = value;
            moveToHead(node);
        }
    }
};

时间复杂度：$O(1)$。哈希表的查询是 $O(1)$ 的，各项操作也都是 $O(1)$ 的。
空间复杂度：$O(capacity)$。我们需要建立哈希表和双向链表，他们的最大大小都是 $O(capacity)$ 的。

心之所向便是光

Leetcode 146.LRU 缓存机制

题目描述：

示例：

提示：

链接：

题目分析

本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可

心之所向便是光

题目描述：

示例：

提示：

链接：

题目分析

本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可

本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可