题目:
请你设计并实现一个满足 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.题目中存放的数据是键值对形式的,所以我们可以采用哈希表(unordered_map)来实现
2.同时,题目要求get()、put()的时间复杂度为O(1),也就是能够快速插入、删除元素,来确保时间复杂度低,最佳的数据结构应该是链表,这里用双向链表最高效
所以,我们需要添加一个双向链表的结构体和无序map来对数据实现LRU缓存。
详细过程参考下面代码:文章来源:https://www.toymoban.com/news/detail-699164.html
Code:文章来源地址https://www.toymoban.com/news/detail-699164.html
class LRUCache {
public:
//双链表的结构体
struct Node
{
int key;
int val;
//前驱和后继指针
Node * prev,*next;
//构造函数
Node():key(0),val(0),prev(nullptr),next(nullptr){}
Node(int m_key,int m_val):key(m_key),val(m_val),prev(nullptr),next(nullptr){}
};
unordered_map<int,Node*> map;//哈希表,用来存储键值对
Node* head;//头节点
Node* tail;//尾节点
int m_capacity;//总容量
int size;//哈希表当前容量
LRUCache(int capacity):m_capacity(capacity),size(0) {
//初始化头尾节点
head=new Node();
tail=new Node();
//构建双向链表
head->next=tail;
tail->prev=head;
}
//获取函数
int get(int key) {
//如果哈希表中不存在键为key,直接返回-1
if(!map.count(key))
{
return -1;
}
//存在key
//获取链表的节点
Node* node=map[key];
remove(node);//删除节点
AddNodeToHead(node);//将当前节点移至头节点之后
return node->val;//返回节点的值
}
void put(int key, int value) {
//如果当前key值已存在
if(map.count(key))
{
//获取节点
Node* node=map[key];
//改变节点的值为新的value
node->val=value;
remove(node);//删除节点
AddNodeToHead(node);//将节点移至头节点之后
}
//不存在,则加入到哈希表中
else
{
//判断容量是否已满
if(size==m_capacity)//满了
{
//获取最近最久未使用的节点,也就是尾节点的前驱节点
Node* removed=tail->prev;
//从哈希表中移除该节点
map.erase(removed->key);
//删除节点
remove(removed);
//当前容量--
size--;
}
//创建新节点
Node* node=new Node(key,value);
AddNodeToHead(node);//将节点移至头节点之后
map[key]=node;//加入哈希表中
size++;//当前容量++
}
}
//删除节点函数
void remove(Node* node)
{
node->prev->next=node->next;
node->next->prev=node->prev;
}
//将节点移至头节点之后
void AddNodeToHead(Node* node)
{
node->prev=head;
node->next=head->next;
head->next->prev=node;
head->next=node;
}
};
到了这里,关于面试题常考:LRU缓存的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!