LRU构造的代码哪里有问题
class ListNode:def __init__(self,key=None,value=None):
self.key = key
self.value = value
self.next = None
self.pre = None
class LRUCache:
#'''使用双向链表进行操作'''#
def __init__(self, capacity: int):
self.capacity = capacity #链表节点总数
self.hashmap = {} #哈希表存储节点的key值，用于指示节点
self.head = ListNode() #定义头结点和尾节点
self.tail = ListNode()
self.head.next = self.tail #初始化链表，头尾结点相接
self.tail.pre = self.head
def move_to_tail(self,key:int):
node = self.hashmap
node.pre.next = node.next#将需要移动到尾部的结点从链表中拎出（相当于在原位置删除）
node.next.pre = node.pre
node.pre = self.tail.pre#将该节点插入到尾节点前面一个位置
node.next = self.tail
self.tail.pre.next = node
self.tail.pre = node
def get(self, key: int) -> int:
if key in self.hashmap:#defaultdict对于不存在的值返回空结点，dict对不存在的值会返回None
self.move_to_tail(key) #把该被访问的结点移到链表尾部
return self.hashmap.value
else:
return -1
def put(self, key: int, value: int) -> None:
if key in self.hashmap:#关键字key已存在于哈希表
self.hashmap.value = value
self.move_to_tail(key) #将更新后的key移动到链表尾部
else:#哈希表不存在该关键字
if len(self.hashmap) == self.capacity:#哈希表已达到最大容量
self.hashmap.pop(self.head.next.key)
self.head.next = self.head.next.next #头结点后删除该节点
self.head.next.pre = self.head
#新结点添加在tail节点之前
new = ListNode()
self.hashmap = new
new.pre = self.tail.pre#将该节点插入到尾节点前面一个位置
new.next = self.tail
self.tail.pre.next = new
self.tail.pre = new
# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)
上述代码哪里有错？半天没看出来 你的代码有几个问题，我帮你指出来：
1. **`move_to_tail`方法的问题：**
node = self.hashmap# 应该是 `node = self.hashmap`, 缺少
2. **`get`方法的问题：**
return self.hashmap.value# 应该是 `return self.hashmap.value`
3. **`put`方法的问题：**
- 更新`hashmap`时，应该是`self.hashmap = new`而不是`self.hashmap = new`。
- 如果达到最大容量时删除节点，不仅要更新链表，还要确保在`hashmap`中删除对应的`key`。
下面是修改后的代码：
class ListNode:
def __init__(self, key=None, value=None):
self.key = key
self.value = value
self.next = None
self.pre = None
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.hashmap = {}
self.head = ListNode()
self.tail = ListNode()
self.head.next = self.tail
self.tail.pre = self.head
def move_to_tail(self, key: int):
node = self.hashmap
node.pre.next = node.next
node.next.pre = node.pre
node.pre = self.tail.pre
node.next = self.tail
self.tail.pre.next = node
self.tail.pre = node
def get(self, key: int) -> int:
if key in self.hashmap:
self.move_to_tail(key)
return self.hashmap.value
else:
return -1
def put(self, key: int, value: int) -> None:
if key in self.hashmap:
self.hashmap.value = value
self.move_to_tail(key)
else:
if len(self.hashmap) == self.capacity:
# Remove the least recently used node
lru = self.head.next
del self.hashmap
self.head.next = lru.next
lru.next.pre = self.head
# Add new node
new = ListNode(key, value)
self.hashmap = new
new.pre = self.tail.pre
new.next = self.tail
self.tail.pre.next = new
self.tail.pre = new
这个版本的代码修复了之前的错误，并实现了LRU缓存的功能。希望这能帮助到你！
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。
页:
[1]