题目
146. 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) 的平均时间复杂度运行。
示例：
输入
[“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
我的代码（C++）
struct ValueStruct {
int _key;
int _value;
ValueStruct* _prev;
ValueStruct* _next;
ValueStruct(int k, int v) {
_key = k;
_value = v;
_prev = nullptr;
_next = nullptr;
}
};
class LRUCache {
private:
int _size;
std::map<int, ValueStruct*> _value_map;
ValueStruct* head;
ValueStruct* tail;
public:
LRUCache(int capacity) {
_size = capacity;
head = nullptr;
tail = nullptr;
}
void printMap() {
for (std::map<int, ValueStruct*>::iterator it = _value_map.begin(); it != _value_map.end(); it++) {
printf("key: %d, val: %d, self: %p, prev: %p, next: %p\n", it->first, it->second->_value, it->second, it->second->_prev, it->second->_next);
}
printf("\n");
}
int get(int key) {
// std::cout << "get: " << key << std::endl;
// printMap();
std::map<int, ValueStruct*>::iterator it = _value_map.find(key);
if (_value_map.empty() || it == _value_map.end()) {
return -1;
}
ValueStruct* currentNode = it->second;
if (head && head != currentNode) {
currentNode->_prev->_next = currentNode->_next;
if (currentNode->_next)
currentNode->_next->_prev = currentNode->_prev;
if (tail && currentNode->_prev && tail == currentNode) {
tail = currentNode->_prev;
}
currentNode->_prev = nullptr;
currentNode->_next = head;
head->_prev = currentNode;
head = currentNode;
}
return currentNode->_value;
}
void put(int key, int value) {
// std::cout << "put: " << key << std::endl;
// printMap();
std::map<int, ValueStruct*>::iterator it = _value_map.find(key);
if(it == _value_map.end()) {
ValueStruct* newValue = new ValueStruct(key, value);
if(_value_map.size() == _size && tail) {
ValueStruct* deleteNode = tail;
tail = tail->_prev;
if (tail) {
tail->_next = nullptr;
}
std::map<int, ValueStruct*>::iterator delete_it = _value_map.find(deleteNode->_key);
if (delete_it != _value_map.end()) {
_value_map.erase(delete_it);
}
if (head == deleteNode) {
head = nullptr;
}
delete deleteNode;
}
if (!tail) {
tail = newValue;
}
newValue->_next = head;
_value_map[key] = newValue;
if (head) {
head->_prev = newValue;
}
head = newValue;
} else {
ValueStruct* currentNode = it->second;
currentNode->_value = value;
if (head && head != currentNode) {
if (currentNode->_prev) {
currentNode->_prev->_next = currentNode->_next;
}
if (currentNode->_next)
currentNode->_next->_prev = currentNode->_prev;
if (tail && tail == currentNode && currentNode->_prev) {
tail = currentNode->_prev;
}
currentNode->_prev = nullptr;
currentNode->_next = head;
head->_prev = currentNode;
head = currentNode;
}
}
}
};
/**
* 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);
*/点评
和官方的想法一样，双向链表+哈希。用双向链表是因为需要维护访问排序，双向链表可以维护一头一尾，同时在哈希表协助下可以方便地调整结构。
我的代码里肯定有很多冗余，表现也中规中矩。
调整链表结构是核心，比较麻烦，不小心就会遗漏步骤或者忘记处理特殊情况。
baddif@gmail.com
AI简历优化站
AI求职跟踪器（建设中）
主站（建设中）
相关平台
Github Issues / Notion / Blog