LRU构造的代码哪里有问题

Terence888

1. class ListNode:
   
2.     def __init__(self,key=None,value=None):
   
3.         self.key = key
   
4.         self.value = value
   
5.         self.next = None
   
6.         self.pre = None
   
7. class LRUCache:
   
8. #'''使用双向链表进行操作'''#
   
9.     def __init__(self, capacity: int):
   
10.         self.capacity = capacity #链表节点总数
    
11.         self.hashmap = {} #哈希表存储节点的key值，用于指示节点
    
12.         self.head = ListNode() #定义头结点和尾节点
    
13.         self.tail = ListNode()
    
14.         
    
15.         self.head.next = self.tail #初始化链表，头尾结点相接
    
16.         self.tail.pre = self.head
    
17.    
    
18.     def move_to_tail(self,key:int):
    
19.         node = self.hashmap[key]
    
20.         node.pre.next = node.next#将需要移动到尾部的结点从链表中拎出（相当于在原位置删除）
    
21.         node.next.pre = node.pre
    
22. 
    
23.         node.pre = self.tail.pre#将该节点插入到尾节点前面一个位置
    
24.         node.next = self.tail
    
25.         self.tail.pre.next = node
    
26.         self.tail.pre = node
    
27. 
    
28. 
    
29. 
    
30.     def get(self, key: int) -> int:
    
31.         if key in self.hashmap:#defaultdict对于不存在的值返回空结点，dict对不存在的值会返回None
    
32.             self.move_to_tail(key) #把该被访问的结点移到链表尾部
    
33.             return self.hashmap[key].value
    
34.         else:
    
35.             return -1
    
36. 
    
37.     def put(self, key: int, value: int) -> None:
    
38.         if key in self.hashmap:#关键字key已存在于哈希表
    
39.             self.hashmap[key].value = value
    
40.             self.move_to_tail(key) #将更新后的key移动到链表尾部
    
41.         else:#哈希表不存在该关键字
    
42.             if len(self.hashmap) == self.capacity:#哈希表已达到最大容量
    
43.                 self.hashmap.pop(self.head.next.key)
    
44.                 self.head.next = self.head.next.next #头结点后删除该节点
    
45.                 self.head.next.pre = self.head
    
46. 
    
47.             #新结点添加在tail节点之前
    
48.             new = ListNode()
    
49.             self.hashmap[new.key] = new
    
50.             new.pre = self.tail.pre#将该节点插入到尾节点前面一个位置
    
51.             new.next = self.tail
    
52.             self.tail.pre.next = new
    
53.             self.tail.pre = new
    
54. 
    
55. # Your LRUCache object will be instantiated and called as such:
    
56. # obj = LRUCache(capacity)
    
57. # param_1 = obj.get(key)
    
58. # obj.put(key,value)

复制代码

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

FishC

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

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

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

复制代码

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

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

复制代码

3. **`put`方法的问题：**
   - 更新`hashmap`时，应该是`self.hashmap[key] = new`而不是`self.hashmap = new`。
   - 如果达到最大容量时删除节点，不仅要更新链表，还要确保在`hashmap`中删除对应的`key`。

下面是修改后的代码：

1. class ListNode:
   
2.     def __init__(self, key=None, value=None):
   
3.         self.key = key
   
4.         self.value = value
   
5.         self.next = None
   
6.         self.pre = None
   
7. 
   
8. class LRUCache:
   
9.     def __init__(self, capacity: int):
   
10.         self.capacity = capacity
    
11.         self.hashmap = {}
    
12.         self.head = ListNode()
    
13.         self.tail = ListNode()
    
14.         
    
15.         self.head.next = self.tail
    
16.         self.tail.pre = self.head
    
17. 
    
18.     def move_to_tail(self, key: int):
    
19.         node = self.hashmap[key]
    
20.         node.pre.next = node.next
    
21.         node.next.pre = node.pre
    
22. 
    
23.         node.pre = self.tail.pre
    
24.         node.next = self.tail
    
25.         self.tail.pre.next = node
    
26.         self.tail.pre = node
    
27. 
    
28.     def get(self, key: int) -> int:
    
29.         if key in self.hashmap:
    
30.             self.move_to_tail(key)
    
31.             return self.hashmap[key].value
    
32.         else:
    
33.             return -1
    
34. 
    
35.     def put(self, key: int, value: int) -> None:
    
36.         if key in self.hashmap:
    
37.             self.hashmap[key].value = value
    
38.             self.move_to_tail(key)
    
39.         else:
    
40.             if len(self.hashmap) == self.capacity:
    
41.                 # Remove the least recently used node
    
42.                 lru = self.head.next
    
43.                 del self.hashmap[lru.key]
    
44.                 self.head.next = lru.next
    
45.                 lru.next.pre = self.head
    
46. 
    
47.             # Add new node
    
48.             new = ListNode(key, value)
    
49.             self.hashmap[key] = new
    
50. 
    
51.             new.pre = self.tail.pre
    
52.             new.next = self.tail
    
53.             self.tail.pre.next = new
    
54.             self.tail.pre = new

复制代码

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

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