35. LRU 缓存

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。

实现LRUCache类：

• LRUCache(int capacity)以正整数作为容量capacity初始化 LRU 缓存
• int get(int key)如果关键字key存在于缓存中，则返回关键字的值，否则返回-1。
• void put(int key, int value)如果关键字key已经存在，则变更其数据值value；如果不存在，则向缓存中插入该组key-value。如果插入操作导致关键字数量超过capacity，则应该逐出最久未使用的关键字。

函数get和put必须以O(1)的平均时间复杂度运行。

双端链表

class Node(object): def __init__(self,key=0,value=0,prev=None,next=None): self.key=key self.value=value self.prev=prev self.next=next class LRUCache(object): def __init__(self, capacity): self.capacity=capacity self.head=Node() self.tail=Node() self.head.next=self.tail self.tail.prev=self.head self.mp={} self.full=0 def _remove_node(self,node): node.prev.next=node.next node.next.prev=node.prev def _add_to_head(self,node): node.next=self.head.next node.prev=self.head self.head.next.prev=node self.head.next=node def _move_to_head(self,node): self._remove_node(node) self._add_to_head(node) def _remove_tail(self): node=self.tail.prev self._remove_node(node) return node def get(self, key): if key in self.mp: self._move_to_head(self.mp[key]) return self.mp[key].value return -1 def put(self, key, value): if key in self.mp: self.mp[key].value=value self._move_to_head(self.mp[key]) else: node=Node(key,value) self.mp[key]=node self.full+=1 self._add_to_head(node) if self.full>self.capacity: cur=self._remove_tail() del self.mp[cur.key] self.full-=1 return cur.value