146. LRU 缓存
题目：
第一次思考：
- 又被难住了
- 想着用两个map实现
- map_val记录键值对数据
- map_pos记录数据在LRU中的实时位置
- 超时了，待优化
实现：
class LRUCache {
public:
int capacity;
int pos=0;
unordered_map<int,int> map_val;
unordered_map<int,int> map_pos;
public:
LRUCache(int capacity) {
this->capacity=capacity;
}
int get(int key) {
int ref=-1;
if (map_val.find(key)!=map_val.end()){
ref=map_val[key];
for (auto [k,p]:map_pos){
if (p>map_pos[key]){
map_pos[k]--;
}
}
map_pos[key]=pos-1;
}
return ref;
}
void put(int key, int value) {
if (map_val.find(key)!=map_val.end()){
map_val[key]=value;
for (auto [k,p]:map_pos){
if (p>map_pos[key]){
map_pos[k]--;
}
}
map_pos[key]=pos-1;
}
else{
if (pos<capacity){
map_val[key]=value;
map_pos[key]=pos;
pos++;
}
else{
for (auto [k,p]:map_pos)
{
if (p==0)
{
map_val.erase(k);
map_pos.erase(k);
break;
}
}
for (auto& [k,p]:map_pos)
{
p--;
}
map_val[key]=value;
map_pos[key]=pos-1;
}
}
}
};
第二次思考：
- 第一次的代码主要耗时在实时维护更新pos表中的信息
- 如果用链表实现的话就不需要每次遍历更新信息了。
- 采用双向链表，之所以用双向链表是为了在删除节点时可以快速找到该节点的前一个节点
- 使用额外的头节点和尾节点两个空节点，之所以使用两个空节点是为了方便在删除和插入节点的时候不需要对第一个节点和最后一个节点进行额外的判断和操作，都可以当成普通节点，减少实现难度。
- 使用map记录下每个key对应的节点，方便快速找到key对应的节点
实现：
class ListNode_pre
{
public:
int key;
int value;
ListNode_pre* next;
ListNode_pre* prev;
public:
ListNode_pre(int k,int v)
{
this->key=k;
this->value=v;
this->next=NULL;
this->prev=NULL;
}
ListNode_pre()
{
this->key=0;
this->value=0;
this->next=NULL;
this->prev=NULL;
}
};
class LRUCache {
public:
int capacity;
ListNode_pre* head;
ListNode_pre* tail;
unordered_map<int,ListNode_pre*> m;
int pos=0;
public:
LRUCache(int capacity) {
this->capacity=capacity;
head=new ListNode_pre();
tail=new ListNode_pre();
head->next=tail;
tail->prev=head;
}
int get(int key) {
int ref=-1;
auto find_key=m.find(key);
if (find_key!=m.end()){
auto node=find_key->second;
ref=node->value;
node->prev->next=node->next;
node->next->prev=node->prev;
node->next=head->next;
head->next->prev=node;
node->prev=head;
head->next=node;
}
return ref;
}
void put(int key, int value) {
auto find_key=m.find(key);
if (find_key!=m.end()){
auto node=find_key->second;
node->value=value;
node->prev->next=node->next;
node->next->prev=node->prev;
node->next=head->next;
head->next->prev=node;
node->prev=head;
head->next=node;
}
else
{
if (pos<capacity)
{
auto node=new ListNode_pre(key,value);
node->next=head->next;
head->next->prev=node;
node->prev=head;
head->next=node;
m[key]=node;
pos++;
}
else
{
auto node=tail->prev;
node->prev->next=tail;
tail->prev=node->prev;
m.erase(node->key);
node->key=key;
node->value=value;
node->next=head->next;
head->next->prev=node;
node->prev=head;
head->next=node;
m[key]=node;
}
}
}
};
