leetcode link: LRU 缓存
请你设计并实现一个满足 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) 的平均时间复杂度运行。
解析：我们需要这么一个数据结构
- 1 在最前面删除
- 2 在最后面加入
- 3 查询为O(1) – 哈希表
- 4 在中间删除，追加到最后为O(1) – 双向链表
综上，我们采用哈希表+双向链表的形式解决该题。
哈希表的key为输入的key，value为链表的节点。
struct Node{
int key, val;
Node *prev, *next;
Node(): key(0), val(0), prev(nullptr), next(nullptr) {};
Node(int _key, int _val):key(_key), val(_val), prev(nullptr), next(nullptr) {};
};
class LRUCache {
public:
Node* head, *tail;
unordered_map map;
int capacity, size;
LRUCache(int _capacity): capacity(_capacity), size(0){
head = new Node();
tail = new Node();
head->next = tail;
tail->prev = head;
}
// 关注两条边
void removeNode(Node* node){
node->prev->next = node->next;
node->next->prev = node->prev;
}
// 四条边,先关注节点，再关注后前
void addHeadNode(Node* node){
node->prev = head;
node->next = head->next;
head->next->prev = node;
head->next = node;
}
int get(int key) {
if (!map.count(key)) return -1;
Node* node = map[key];
removeNode(node);
addHeadNode(node);
return node->val;
}
void put(int key, int value) {
if (map.count(key)){
Node* node = map[key];
node->val = value;
removeNode(node);
addHeadNode(node);
}else{
if (capacity == size){
Node* remove_node = tail->prev;
map.erase(remove_node->key);
removeNode(remove_node);
size--;
}
Node* insert_node = new Node(key, value);
map[key] = insert_node;
addHeadNode(insert_node);
size++;
}
}
};
/**
* 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);
*/ 一些细节：
- 1 双向链表需要建立head和tail两个虚拟节点，初始化时head和tail连接。
- 2 双向链表增加一个节点时，有4个边操作。
- 先对node节点左右边进行操作。
- 在对node后一个节点进行操作，最后对node前一个节点进行操作。
- 3 不管是put还是get操作，一旦命中哈希，则需要将该节点从中间删除，插入双向链表的最前方。
- 4 put需要行新增节点时，先进行容量判断，再增加节点。