LeetCode 146. [Python] LRU Cache
原题链接
中等
作者:
徐辰潇
,
2021-01-26 01:09:19
,
所有人可见
,
阅读 329
#Define a double linkedin node
#use a dict to store key as key and node address as value
class Node:
def __init__(self, key, val):
self.key = key
self.val = val
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.dict = {}
self.head = Node(-1, -1)
self.tail = Node(-1, -1)
self.head.next = self.tail
self.tail.prev = self.head
def get(self, key: int) -> int:
#TC: O(1)
if key not in self.dict:
return -1
cur = self.dict[key]
cur.prev.next = cur.next
cur.next.prev = cur.prev
self.move_to_tail(cur)
return cur.val
def put(self, key: int, value: int) -> None:
#TC: O(1)
if key in self.dict:
cur = self.dict[key]
cur.val = value
Prev = cur.prev
Next = cur.next
Prev.next = Next
Next.prev = Prev
self.move_to_tail(cur)
else:
New = Node(key, value)
self.dict[key] = New
self.move_to_tail(New)
if len(self.dict) > self.capacity:
First = self.head.next
First_next = First.next
First_next.prev = self.head
self.head.next = First_next
del self.dict[First.key]
return key
def move_to_tail(self, cur):
Prev = self.tail.prev
Prev.next = cur
cur.prev = Prev
cur.next = self.tail
self.tail.prev = cur
# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)