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

【LeetCode】每日一题：LRU缓存

news 2025/7/13 11:05:47

请你设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该逐出最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

解题思路

看的题解，双向链表+哈希表+假链表头尾

AC代码

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.moveToHead(node)return node.valuedef put(self, key: int, value: int) -> None:if key not in self.cache:# 如果 key 不存在，创建一个新的节点node = DLinkedNode(key, value)# 添加进哈希表self.cache[key] = node# 添加至双向链表的头部self.addToHead(node)self.size += 1if self.size > self.capacity:# 如果超出容量，删除双向链表的尾部节点removed = self.removeTail()# 删除哈希表中对应的项self.cache.pop(removed.key)self.size -= 1else:# 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部node = self.cache[key]node.value = valueself.moveToHead(node)def addToHead(self, node):node.next = self.head.nextnode.prev = self.headself.head.next.prev = nodeself.head.next = nodedef removedNode(self, node):node.prev.next = node.nextnode.next.prev = node.prevdef moveToHead(self, node):self.removedNode(node)self.addToHead(node)def removeTail(self):node = self.tail.prevself.removedNode(node)return node# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)