(nice!!!)(LeetCode 面试经典 150 题) 146. LRU 缓存 (哈希表+双向链表)

思路：哈希表+双向链表，时间复杂度0(n)。

get、put时间复杂度必须为0(n)，那么就得用空间换时间。双向链表来记录每一个节点node（key-value），哈希表来记录每一个key所对应的节点node。
在get、put时，先判断哈希表mp里是否存储了key，而双向链表是维护每一个节点的访问顺序。

C++版本：

class LRUCache {
// 节点node
typedef struct Node{int key;int val;Node * prev;Node * next;Node(int k,int v):key(k),val(v){}
}node;// 哈希表的最大容量
int capt;
// 双向链表的哨兵节点
node *head;
// 哈希表
unordered_map<int,node *> mp;public:// 将双向链表的节点x删除void deletee(node * x){x->prev->next=x->next;x->next->prev=x->prev;}// 将节点x插入到双向链表的头节点，也就是哨兵节点head的右边void insertt(node * x){x->prev=head;x->next=head->next;x->prev->next=x;x->next->prev=x;}// 初始化内置函数LRUCache(int capacity) {capt=capacity;head=new node(0,0);head->next=head;head->prev=head;}int get(int key) {if(mp.find(key)==mp.end()) return -1;deletee(mp[key]);insertt(mp[key]);return mp[key]->val;}void put(int key, int value) {// 哈希表存在keyif(mp.find(key)!=mp.end()){node * tmp=mp[key];tmp->val=value;deletee(tmp);insertt(tmp);return ;}// 哈希表不存在keymp[key]=new node(key,value);insertt(mp[key]);// 哈希表容量大于capacityif(mp.size()>capt){// 通过哨兵节点head找到最后一个节点node * bak=head->prev;deletee(bak);mp.erase(bak->key);delete bak;}}
};/*** 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);*/

JAVA版本：

class LRUCache {class node{int key;int val;node prev,next;node(int k,int v){key=k;val=v;}}int capt;node head=new node(0,0);Map<Integer,node> mp=new HashMap<>();void deletee(node  x){x.prev.next=x.next;x.next.prev=x.prev;}void insertt(node x){x.prev=head;x.next=head.next;x.prev.next=x;x.next.prev=x;}LRUCache(int capacity) {capt=capacity;head.next=head;head.prev=head;}int get(int key) {if(mp.containsKey(key)==false) return -1;deletee(mp.get(key));insertt(mp.get(key));return mp.get(key).val;}void put(int key, int value) {if(mp.containsKey(key)==true){node tmp=mp.get(key);tmp.val=value;deletee(tmp);insertt(tmp);return ;}mp.put(key,new node(key,value));insertt(mp.get(key));if(mp.size()>capt){node bak=head.prev;deletee(bak);mp.remove(bak.key);}}
}/*** 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);*/

GO版本：

type node struct{key,val    intprev,next  *node
}type LRUCache struct {capacity inthead     *nodemp       map[int]*node
}func Constructor(capacity int) LRUCache {nd:=&node{key:0,val:0,}nd.prev=ndnd.next=ndreturn LRUCache{capacity :capacity,head     :nd,mp       :map[int]*node{},}
}func (this *LRUCache) deletee(x *node){x.prev.next=x.nextx.next.prev=x.prev
}func (this *LRUCache) insertt(x *node){x.prev=this.headx.next=this.head.nextx.prev.next=xx.next.prev=x
}func (this *LRUCache) getNode(key int) *node{nd,ok :=this.mp[key]if !ok {return nil}this.deletee(nd)this.insertt(nd)return nd
}func (this *LRUCache) Get(key int) int {nd:=this.getNode(key)if nd==nil {return -1}return nd.val
}func (this *LRUCache) Put(key int, value int)  {nd:=this.getNode(key)if nd!=nil {nd.val=valuereturn}this.mp[key]=&node{key :key,val :value,}this.insertt(this.mp[key])if len(this.mp)>this.capacity {bak:=this.head.prevthis.deletee(bak)delete(this.mp,bak.key)}return 
}/*** Your LRUCache object will be instantiated and called as such:* obj := Constructor(capacity);* param_1 := obj.Get(key);* obj.Put(key,value);*/