设计和构建一个“最近最少使用”缓存，该缓存会删除最近最少使用的项目。缓存应该从键映射到值(允许你插入和检索特定键对应的值)，并在初始化时指定最大容量。当缓存被填满时，它应该删除最近最少使用的项目。
它应该支持以下操作：
get 和 写入数据 put 。get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。get和put的时间复杂度为O(1)LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 该操作会使得密钥 2 作废
cache.get(2); // 返回 -1 (未找到)
cache.put(4, 4); // 该操作会使得密钥 1 作废
cache.get(1); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.get(4); // 返回 4
class LRUCache {
private:
int capacity;
std::deque<int> dq;
std::unordered_map<int, int> mp;
public:
LRUCache(int capacity) : capacity(capacity) {}
int get(int key) { // 若元素存在则将该元素移到队尾
if (mp.find(key) != mp.end()) {
dq.erase(std::remove(dq.begin(), dq.end(), key), dq.end());
dq.push_back(key);
return mp[key];
}
return -1;
}
void put(int key, int value) {
if (mp.find(key) != mp.end()) {// 如果 key 已存在，更新 value，并调整到队尾
mp[key] = value;
dq.erase(std::remove(dq.begin(), dq.end(), key), dq.end());
dq.push_back(key);
} else {
if (dq.size() == capacity) {
int lru_key = dq.front();
mp.erase(lru_key);
dq.pop_front();
}
mp[key] = value;
dq.push_back(key);
}
}
};
解法1的效率十分低，而且没有满足时间复杂度O（1）的条件，效率只击败了5%，我们想想要如何实现O（1），什么数据结构支持O（1）维护两端元素呢，我们可以用双向链表来实现。
使用双向链表+哈希表维护，表头维护最近使用的元素，表尾维护最久未使用的元素。这里我们要使用双向链表实现在表头添加一个元素、删除某个节点这两个操作。
对于 get 操作，首先判断 key是否存在：如果 key 不存在，则返回 -1；如果 key 存在，则 key 对应的节点是最近被使用的节点。通过哈希表定位到该节点在双向链表中的位置，并将其移动到双向链表的头部，最后返回该节点的值。
对于 put 操作，首先判断 key 是否存在：如果 key 不存在，使用 key 和 value 创建一个新的节点，在双向链表的头部添加该节点，并将 key 和该节点添加进哈希表中。然后判断双向链表的节点数是否超出容量，如果超出容量，则删除双向链表的尾部节点，并删除哈希表中对应的项；如果 key 存在，则与 get 操作类似，先通过哈希表定位，再将对应的节点的值更新为 value，并将该节点移到双向链表的头部。
class Node {
public:
int key, value;
Node *prev, *next;
// 构造函数
Node() : key(0), value(0), prev(nullptr), next(nullptr) {}
Node(int _key, int _value) : key(_key), value(_value), prev(nullptr), next(nullptr) {}
};
class LRUCache {
private:
std::unordered_map<int, Node*> cache;
Node* dummy; // 头节点 表头维护最近使用的 表尾维护最久未使用的
int capacity;
// 删除一个节点
void remove(Node *p) {
p->prev->next = p->next;
p->next->prev = p->prev;
}
// 表头添加一个节点
void push_front(Node *p) {
p->prev = dummy;
p->next = dummy->next;
p->prev->next = p;
p->next->prev = p;
}
Node* get_node(int key) {
auto it = cache.find(key);
if (it == cache.end()) return nullptr;
auto node = it->second;
remove(node); // 将元素移出
push_front(node); // 放在表头
return node;
}
public:
LRUCache(int capacity) {
this->capacity = capacity;
dummy = new Node();
dummy->next = dummy;
dummy->prev = dummy;
}
int get(int key) {
auto node = get_node(key);
return node ? node->value : -1;
}
void put(int key, int value) {
auto node = get_node(key);
if (node) { //若存在该元素
node->value = value; // 更新value
return ;
}
cache[key] = node = new Node(key, value);
push_front(node); // 放在表头
if (cache.size() > capacity) { // 超容量
auto back = dummy->prev;
cache.erase(back->key);
remove(back); //去掉尾部元素
delete back; // 释放内存
}
}
};
/**
* 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);
*/
版权说明：如非注明，本站文章均为 扬州驻场服务-网络设备调试-监控维修-南京泽同信息科技有限公司 原创，转载请注明出处和附带本文链接。
请在这里放置你的在线分享代码