146. LRU 缓存机制
题目描述
思路分析
双向链表模拟
+
h
a
s
h
+hash
+hash
哈希表记录 已经出现的
k
e
y
key
key的位置
双链表维护缓存队列，按照操作时间顺序，最近的放最前。
两个辅助函数
r
e
m
o
v
e
remove
remove和
i
n
s
e
r
t
insert
insert
r
e
m
o
v
e
:
remove:
remove:把一个节点从缓存队列中删除
i
n
s
e
r
t
:
insert:
insert:把一个节点插入到缓存队列头部
代码实现
class LRUCache {
public:
struct Node{
int key,val;
Node *l,*r;
Node(int _key,int _val):key(_key),val(_val),l(NULL),r(NULL){};
}*L,*R;
unordered_map<int,Node*> hash;
int n;
LRUCache(int capacity) {
n=capacity;
L=new Node(-1,-1),R=new Node(-1,-1);
L->r=R;
R->l=L;
}
void remove(Node* p){
p->r->l=p->l;
p->l->r=p->r;
}
void insert(Node* p){
p->r=L->r;
p->l=L;
L->r->l=p;
L->r=p;
}
int get(int key) {
if(hash.count(key)==0) return -1;
auto p=hash[key];
remove(p); //删掉
insert(p); //插入到最左侧
return p->val;
}
void put(int key, int value) {
if(hash.count(key)){
auto p=hash[key];
p->val=value;
remove(p);
insert(p);
}
else{
if(hash.size()==n){
auto p=R->l;
remove(p);
hash.erase(p->key);
delete p;
}
auto p=new Node(key,value);
hash[key]=p;
insert(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);
*/