此题看题解

题目链接

class ListNode:def __init__(self, key=None, value=None):self.key = keyself.value = valueself.prev = Noneself.next = Noneclass LRUCache:def __init__(self, capacity: int):self.capacity = capacityself.cache = {}self.head = ListNode()self.tail = ListNode()self.head.next = self.tailself.tail.prev = self.headdef get(self, key: int) -> int:if key in self.cache:node = self.cache[key]self._move_to_head(node)return node.valueelse:return -1def put(self, key: int, value: int) -> None:if key in self.cache:node = self.cache[key]node.value = valueself._move_to_head(node)else:if len(self.cache) == self.capacity:self._remove_tail()node = ListNode(key, value)self.cache[key] = nodeself._add_to_head(node)def _move_to_head(self, node: ListNode) -> None:self._remove_node(node)self._add_to_head(node)def _remove_node(self, node: ListNode) -> None:node.prev.next = node.nextnode.next.prev = node.prevdef _add_to_head(self, node: ListNode) -> None:node.prev = self.headnode.next = self.head.nextself.head.next.prev = nodeself.head.next = nodedef _remove_tail(self) -> None:node = self.tail.prevself._remove_node(node)del self.cache[node.key]
# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)