leetcode LRU Cache python

时间:2021-03-26 06:16:44
class Node(object):
def __init__(self,k,x):
self.key=k
self.val=x
self.prev=None
self.next=None
class DoubleLinkedList(object):
def __init__(self):
self.tail=None
self.head=None
def isEmpty(self):
return not self.None
def removeLast(self):
self.remove(self.tail)
def remove(self,node):
if self.head == self.tail:
self.head,self.tail = None,None
return
if node == self.head:
node.next.prev=None
self.head=node.next
return
if node == self.tail:
node.prev.next=None
self.tail=node.prev
return
node.prev.next=node.next
node.next.prev=node.prev
def addFirst(self,node):
if not self.head:
self.head=self.tail=node
node.prev=node.next=None
return
node.next=self.head
self.head.prev=node
self.head=node
node.prev=None class LRUCache(object): def __init__(self, capacity):
"""
:type capacity: int
"""
self.capacity=capacity
self.size=0
self.p=dict()
self.cache=DoubleLinkedList() def get(self, key):
"""
:rtype: int
"""
if (key in self.p) and self.p[key]:
self.cache.remove(self.p[key])
self.cache.addFirst(self.p[key])
return self.p[key].val
else:
return -1 def set(self, key, value):
"""
:type key: int
:type value: int
:rtype: nothing
"""
if key in self.p:
self.cache.remove(self.p[key])
self.cache.addFirst(self.p[key])
self.p[key].val=value
else:
node=Node(key,value)
self.p[key]=node
self.cache.addFirst(node)
self.size+=1
if self.size > self.capacity:
self.size-=1
del self.p[self.cache.tail.key]
self.cache.removeLast()

@link https://github.com/Linzertorte/LeetCode-in-Python/blob/master/LRUCache.py