问题url
https://leetcode-cn.com/problems/lru-cache/
答案
# -*- coding: utf-8 -*-
cg = "cgnb"
class linknode:
def __init__(self,key:int,value:int):
self.key = key
self.value = value
self.prenode = None
self.nextnode = None
class LRUCache:
def __init__(self, capacity: int):
self.dict1 = {}
self.capacity = capacity
self.headnode = None
self.lastnode = None
def get(self, key: int) -> int:
if key in self.dict1:
node = self.dict1[key]
value = self.dict1[key].value
pre_node = node.prenode
next_node = node.nextnode
if (pre_node is None) & (next_node is None):
pass
else:
if not pre_node is None:
if next_node is None:
pre_node.nextnode = node
else:
pre_node.nextnode = next_node
else :
self.headnode = next_node
if not next_node is None:
next_node.prenode = pre_node
if self.lastnode != node:
lastnode = self.lastnode
lastnode.nextnode = node
node.prenode = lastnode
node.nextnode = None
self.lastnode = node
return value
else:
return -1
def put(self, key: int, value: int) -> None:
if len(self.dict1) == 0:
node = linknode(key,value)
self.dict1[key] = node
self.headnode = node
self.lastnode = node
elif key in self.dict1:
self.get(key)
self.dict1[key].value = value
elif len(self.dict1)<self.capacity:
node = linknode(key,value)
self.dict1[key] = node
node.prenode = self.lastnode
self.lastnode.nextnode = node
self.lastnode = node
else:
del_key = self.headnode.key
self.headnode = self.dict1[del_key].nextnode
del self.dict1[del_key]
node = linknode(key,value)
self.dict1[key] = node
node.prenode = self.lastnode
self.lastnode.nextnode = node
self.lastnode = node
# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)