LeetCode 146. LRU缓存机制
原题链接
中等
作者:
linux_2019
,
2019-09-20 10:42:52
,
所有人可见
,
阅读 805
C++ 代码
class LRUCache {
public:
struct node {
int key;
int val;
struct node * prev;
struct node * next;
node(){
key=0;
val=0;
prev=nullptr;
next=nullptr;
}
};
struct node *hr,*hu;
int n;
unordered_map<int ,struct node *> buck;
~LRUCache()
{
while(hr->next!=hr)
{
struct node * p=hr->next;
delete_node(p);
delete p;
}
delete hr;
while(hu->next!=hu)
{
struct node *p=hu->next;
delete_node(p);
delete p;
}
delete hu;
}
void insert_node(struct node * h, struct node * p)
{
p->next=h->next;
h->next=p;
p->prev=h;
p->next->prev=p;
}
void delete_node(struct node * p)
{
p->next->prev=p->prev;
p->prev->next=p->next;
}
LRUCache(int capacity) {
n=capacity;
hr=new node();
hr->prev=hr->next=hr;
hu=new node ();
hu->prev=hu->next=hu;
for(int i=0;i<n;i++)
{
struct node * p=new node();
insert_node(hr,p);
}
}
int get(int key) {
if(buck[key])
{
struct node *p=buck[key];
int val=p->val;
delete_node(p);
insert_node(hu,p);
return val;
}
return -1;
}
void put(int key, int value) {
if(buck[key])
{
struct node * p=buck[key];
p->val=value;
delete_node(p);
insert_node(hu,p);
return ;
}
if(!n)
{
n++;
struct node * p=hu->prev;
buck[p->key]=0;
delete_node(p);
insert_node(hr,p);
}
n--;
struct node * p=hr->next;
p->key=key;
p->val=value;
buck[p->key]=p;
delete_node(p);
insert_node(hu,p);
}
};
/**
* 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);
*/