LRU缓存

Leetcode热题100

发布日期: 2023-05-17

更新日期: 2023-05-17

文章字数: 1k

阅读时长: 4 分

描述

请你设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该逐出最久未使用的关键字。
函数 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]

解释
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 <= 10000
0 <= value <= 105
最多调用 2 * 105 次 get 和 put

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/lru-cache
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

LRU Cache问题的解决方案通常使用哈希表和双向链表来实现。哈希表用于快速查找元素，而双向链表用于存储元素的顺序，并且可以在O(1)时间内将元素放到队列头部。

C++代码

#include <unordered_map>

class LRUCache {
public:
    LRUCache(int capacity) {
        size = capacity;
    }

    int get(int key) {
        // 如果哈希表中不存在该键，则返回 -1
        if (cache.find(key) == cache.end()) {
            return -1;
        }
        // 移动到链表的开头
        auto it = cache[key];
        int val = it->second;
        cacheList.erase(it);
        cacheList.push_front({key, val});
        cache[key] = cacheList.begin();
        return val;
    }

    void put(int key, int value) {
        // 如果键已经存在，则更新其值并移动到链表的开头
        if (cache.find(key) != cache.end()) {
            auto it = cache[key];
            cacheList.erase(it);
            cacheList.push_front({key, value});
            cache[key] = cacheList.begin();
        }
        // 如果键不存在，则插入该键值对
        else {
            // 如果缓存已满，则删除链表末尾的节点
            if (cache.size() == size) {
                auto last = cacheList.back();
                cacheList.pop_back();
                cache.erase(last.first);
            }
            cacheList.push_front({key, value});
            cache[key] = cacheList.begin();
        }
    }

private:
    int size;
    std::list<std::pair<int, int>> cacheList;
    std::unordered_map<int, std::list<std::pair<int, int>>::iterator> cache;
};