LRU构造的代码哪里有问题

Terence888

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[key]
        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[key].value
        else:
            return -1

    def put(self, key: int, value: int) -> None:
        if key in self.hashmap:#关键字key已存在于哈希表
            self.hashmap[key].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.key] = 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)

上述代码哪里有错？半天没看出来

FishC

你的代码有几个问题，我帮你指出来：

1. **`move_to_tail`方法的问题：**

node = self.hashmap  # 应该是 `node = self.hashmap[key]`, 缺少[key]

2. **`get`方法的问题：**

return self.hashmap.value  # 应该是 `return self.hashmap[key].value`

3. **`put`方法的问题：**
   - 更新`hashmap`时，应该是`self.hashmap[key] = 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[key]
        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[key].value
        else:
            return -1

    def put(self, key: int, value: int) -> None:
        if key in self.hashmap:
            self.hashmap[key].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[lru.key]
                self.head.next = lru.next
                lru.next.pre = self.head

            # Add new node
            new = ListNode(key, value)
            self.hashmap[key] = new

            new.pre = self.tail.pre
            new.next = self.tail
            self.tail.pre.next = new
            self.tail.pre = new

这个版本的代码修复了之前的错误，并实现了LRU缓存的功能。希望这能帮助到你！

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。