当前位置：首页 > web >正文

力扣刷题Day 37：LRU 缓存（146）

web 2025/5/9 17:53:50

1.题目描述

2.思路

方法1：直接用Python封装好的数据结构OrderedDict（兼具哈希表与双向链表的数据结构）。

方法2：哈希表辅以双向链表。

3.代码（Python3）

方法1：

class LRUCache(collections.OrderedDict):def __init__(self, capacity: int):super().__init__()self.capacity = capacitydef get(self, key: int) -> int:if key not in self:return -1self.move_to_end(key)return self[key]def put(self, key: int, value: int) -> None:if key in self:self.move_to_end(key)self[key] = valueif len(self) > self.capacity:self.popitem(last=False)

方法2：

class DLinkedNode:def __init__(self, key=0, value=0):self.key = keyself.value = valueself.prev = Noneself.next = Noneclass LRUCache:def __init__(self, capacity: int):self.cache = dict()# 伪头和伪尾self.head = DLinkedNode()self.tail = DLinkedNode()self.head.next = self.tailself.tail.prev = self.headself.capacity = capacityself.size = 0def get(self, key: int) -> int:if key not in self.cache:return -1node = self.cache[key]self.move_to_head(node)return node.valuedef put(self, key: int, value: int) -> None:print(self.size, self.capacity)if key not in self.cache:node = DLinkedNode(key, value)self.cache[key] = nodeself.add_to_head(node)self.size += 1if self.size > self.capacity:removed = self.remove_tail()self.cache.pop(removed.key)self.size -= 1else:node = self.cache[key]node.value = valueself.move_to_head(node)def add_to_head(self, node):node.prev = self.headnode.next = self.head.nextself.head.next.prev = nodeself.head.next = nodedef remove_node(self, node):node.prev.next = node.nextnode.next.prev = node.prevdef move_to_head(self, node):self.remove_node(node)self.add_to_head(node)def remove_tail(self):node = self.tail.prevself.remove_node(node)return node