leetCode 146. LRU 缓存

146. 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)的平均时间复杂度运行。

示例：

输入["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]输出[null, null, null, 1, null, -1, null, -1, 3, 4]解释LRUCache lRUCache = new LRUCache(2); lRUCache.put(1, 1); // 缓存是 {1=1} lRUCache.put(2, 2); // 缓存是 {1=1, 2=2} lRUCache.get(1); // 返回 1 lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3} lRUCache.get(2); // 返回 -1 (未找到) lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3} lRUCache.get(1); // 返回 -1 (未找到) lRUCache.get(3); // 返回 3 lRUCache.get(4); // 返回 4

提示：

• 1 <= capacity <= 3000
• 0 <= key <= 10000
• 0 <= value <= 105
• 最多调用2 * 105次get和put

class LinkList: def __init__(self,key,value): self.key=key self.value=value self.next=None self.prev=None class LRUCache: def __init__(self, capacity: int): self.d={} self.capacity=capacity self.head=LinkList(0,0) self.tail=LinkList(0,0) self.head.next=self.tail self.tail.prev=self.head def add(self,node): self.tail.prev.next=node node.prev=self.tail.prev node.next=self.tail self.tail.prev=node def remove(self,node): node.prev.next=node.next node.next.prev=node.prev def update(self,node): self.remove(node) self.add(node) def get(self, key: int) -> int: if key in self.d: self.update(self.d[key]) # print(self.head.next.value) # print(self.tail.prev.value) return self.d[key].value else: # print(self.head.next.value) # print(self.tail.prev.value) return -1 def put(self, key: int, value: int) -> None: if key in self.d: self.d[key].value=value self.update(self.d[key]) else: node=LinkList(key,value) self.d[key]=node self.add(self.d[key]) if len(self.d)>self.capacity: self.d.pop(self.head.next.key) self.remove(self.head.next) # print(self.head.next.value) # print(self.tail.prev.value) # Your LRUCache object will be instantiated and called as such: # obj = LRUCache(capacity) # param_1 = obj.get(key) # obj.put(key,value)