146.LRU缓存

双向链表+哈希表

class LRUCache {
public://1、定义双向链表结构、容量、哈希表等LRU数据成员struct Node{int key,value;Node *left,*right;Node(int _key,int _value):key(_key),value(_value),left(NULL),right(NULL){}}*L,*R;int n;unordered_map<int,Node*> ump;//2、初始化LRU缓冲，容量为capacityLRUCache(int capacity) {n=capacity;//L、R的分配内存及初始化L=new Node(-1,-1);R=new Node(-1,-1);L->right=R;R->left=L; }//3、定义insert、remove操作void remove(Node *p){p->left->right=p->right;p->right->left=p->left;}//链表左侧为活跃节点，insert位置void insert(Node* p){L->right->left=p;p->right=L->right;p->left=L;L->right=p;}int get(int key) {if(ump.count(key)==0) return -1;Node *p=ump[key];remove(p);insert(p);return p->value;}void put(int key, int value) {if(ump.find(key)!=ump.end()){Node* p=ump[key];remove(p);insert(p);p->value=value;}else{if(ump.size()==n){Node *tmp=R->left;ump.erase(tmp->key);remove(tmp);delete tmp;}Node *p=new Node(key,value);insert(p);ump[key]=p;}}
};