LeetCode 146. LRU 缓存

原题链接

难度：$middle$

---

题目描述

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。

实现 $LRUCache$ 类：

• $LRUCache(intcapacity)$ 以 正整数 作为容量 $capacity$ 初始化 LRU 缓存
• $intget(intkey)$ 如果关键字 $key$ 存在于缓存中，则返回关键字的值，否则返回 $-1$ 。
• $voidput(intkey,intvalue)$ 如果关键字 $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<=10^5$
• 最多调用 $2\ast 10^5$ 次 $get$ 和 $put$

---

算法

(双链表 + 哈希) $O(1)$

使用一个双链表和一个哈希表：

• 使用双链表存储节点；
• 哈希表动态存储key对应的链表中的节点地址；

初始化：

双链表插入 n 个节点，n 是缓存大小；
哈希表为空；

get(key)：

首先用哈希表判断key是否存在：

• 如果key存在，则返回对应的value，同时将key对应的节点在当前位置输出并且放到双链表的最左侧；
• 如果key不存在，则返回-1；

set(key, value)：

首先用哈希表判断key是否存在：

• 如果key存在，则修改对应的value，同时将key对应的节点放到双链表的最左侧；
• 如果key不存在：
  • 如果缓存已满，则删除双链表最右侧的节点（上次使用时间最老的节点），同时更新三个数据结构；
  • 否则，插入(key, value)：创建一个新的节点，并对其赋值(key, val)，然后插入到双链表的最左侧，同时个别更新哈希表。

时间复杂度

双链表和哈希表的增删改查操作的时间复杂度都是 $O(1)$，所以 get 和 set 操作的时间复杂度也都是 $O(1)$

C++ 代码

class LRUCache {
public:struct Node {int key, val;Node *left, *right;Node(int _key, int _val): key(_key), val(_val), left(NULL), right(NULL) {}}*L, *R;unordered_map<int, Node*> hash;int n;//从当前位置删除该节点void remove(Node* p) {p->right->left = p->left;p->left->right = p->right;}//把节点插入在双链表的最前端void insert(Node* p) {p->right = L->right;p->left = L;L->right->left = p;L->right = p;}LRUCache(int capacity) {n = capacity;L = new Node(-1, -1), R = new Node(-1, -1);L->right = R, R->left = L;}int get(int key) {if (hash.count(key) == 0) return -1;auto p = hash[key];remove(p);insert(p);return p->val;}void put(int key, int value) {if (hash.count(key)) {auto p = hash[key];p->val = value;remove(p);insert(p);} else {if (hash.size() == n) {auto p = R->left;remove(p);hash.erase(p->key);delete p;}auto p = new Node(key, value);hash[key] = p;insert(p);}}
};/*** 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);*/