2025/8/1

题目（Medium）：

---

我的思路：

首先要搞清楚这题想要我们做什么。

什么是LRU：在这题可以理解成，在给定容量的情况下，如果新加入数据的时候会超出容量大小。那就需要删除里面的一个元素来腾出空间，而删除的元素的特征是最久没有被操作过的元素

而这题让我们实现的方法有：

①初始化

对于初始化，我们应该在这里定义我们需要的数据结构

②get方法

对于get方法，我们应该在这里快速获取到键对应的值

③put方法

对于put方法，我们需要根据当前的容量选择是直接加入新的元素还是先删除最久没有使用的元素再加入新的元素。

综上可知我们的主要需求有

①快速随机查询

②快速删除最久没使用的元素

• 对于需求①，我们可以很快地想到哈希表，它的查询时间复杂度是O（1）
• 对于需求②，我一开始想到的是最小堆，也就是根节点总是在最上层表示，因此避免了我们一个一个去比较的麻烦。但是它的动态变化性不是很好。那还有没有什么我们可以一键就删除在最开头的元素的数据结构呢？这个时候我们就想到了链表

• 

• 而且这也同时让我们可以想到，越在链表末尾的节点是越不容易被删除的，越在链表接近开头的位置越容易被删除。因此我们还可以把最新被操作过的节点移动到链表末尾去，而要执行这个操作往往需要获取节点的前后节点，所以我们考虑使用双向链表。

再简单总结一下上面的思考得到的就是：

①数据结构使用哈希表和链表（哈希表保存的是key:节点）

②每次最新被访问的元素移动到链表的末尾去

③新计入的元素移动到链表的末尾去

④要删除元素的时候把头节点越过删除节点

具体代码如下：

1.初始化：

class ListNode:
    def __init__(self, key=-1, val=0, next=None, prev=None):
        self.key = key
        self.val = val
        self.next = next
        self.prev = prev    #使用双向链表

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        # 使用哈希表实现 O(1) 查找
        self.key_to_node = {}
        
        # 创建哑节点并初始化为双向链表
        self.head = ListNode()
        self.tail = ListNode()
        self.head.next = self.tail
        self.tail.prev = self.head
        self.curNum = 0

初始化哈希表和双向链表，并分配头尾哑节点

2.Get方法：

def get(self, key: int) -> int:
        #从哈希表中查找该节点是否存在
        if key in self.key_to_node:
            #存在则把这个节点放到末尾
            self.moveToTail(self.key_to_node[key])
            #然后返回它的值
            return self.key_to_node[key].val
        else:
            #不存在就直接返回-1
            return -1

对于把节点移动到末尾的具体方法实现我们不在这里写

3.Put方法

  def put(self, key: int, value: int) -> None:
        #先检查当前节点是否已经存在
        if key in self.key_to_node:
            #先获取这个节点
            node = self.key_to_node[key]
            #已经存在就修改这个节点的值
            node.val = value
            #并把它挪到末尾
            self.moveToTail(node)
            return

        #还不存在就说明需要新增
        #先判断当前容量有没有满
        if self.curNum >= self.capacity:
            #满了则把头结点指向的节点淘汰移除
            self.outNode()
            #然后再放入尾节点的前面
            self.addToTail(ListNode(key,value))
        else:
            #没有满就直接放入尾节点前面
            self.addToTail(ListNode(key,value))
            self.curNum += 1

• 和get里一样，先把整体的逻辑写了，移动到末尾、淘汰首个元素、新增到末尾等具体方法在后续再编写
• 注意这里新增之前要检查一下这个key是否已经存在，已经存在了就直接修改这个key值，并把这个节点移动到末尾（你看，这里就可以复用到上面移动到末尾的方法了）

4.其他方法

4.1.移动到末尾

#用于把一个节点移动到链表末尾位置的方法
    def moveToTail(self, node:ListNode):
        if node.next == self.tail:
            #如果这个节点已经在末尾，那就不用再移动了
            return

        #首先把它从当前的位置移除
        # print("当前节点：",node.key, node.val)
        prev = node.prev
        print(prev.key,prev.val)
        nxt = node.next
        print(nxt.key, nxt.val)
        prev.next = nxt
        nxt.prev = prev
        
        #之后把它接到尾节点的前面
        tailPrev = self.tail.prev
        #先往后连接
        tailPrev.next = node
        node.next = self.tail
        #再往前连接
        self.tail.prev = node
        node.prev = tailPrev

注意它是双向链表，所以前后都要进行连接

4.2.淘汰首元素

 #淘汰在最前面的节点
    def outNode(self):
        head = self.head
        tail = self.tail
        if head.next == tail:
            #说明当前没有需要淘汰的节点
            return

        #从哈希表和链表中都移除
        self.key_to_node.pop(head.next.key)

        #同时更新后继和前驱
        head.next.next.prev = head
        head.next = head.next.next

• 这里也是记得同时更新前驱和后继节点
• 记得同时从链表和哈希表删除

4.3.新增到末尾

 #新加入节点，并放置到末尾
    def addToTail(self, node:ListNode):
        #先加入哈希表
        self.key_to_node[node.key] = node

        #然后再加入链表结尾
        #先获取尾节点和尾节点的前驱节点
        tail = self.tail
        prev = tail.prev
        #先往后连接
        prev.next = node
        node.next = tail
        #再往前连接
        tail.prev = node
        node.prev = prev 

记得同时加入哈希表和链表中

---

总结： 

①题目整体的实现逻辑并不是很复杂，复杂的是逻辑的流程比较多，需要一开始首先分析好各个需求，采用合适的数据结构，并确定对应需要的辅助方法来实现。因此不能边想边做，而是要想好想全面了再一鼓作气写下去

②对于单个方法中，我们只考虑大体的逻辑，对于细小的实现细节但是又需要较多代码的部分我们可以让他先以一个方法替代，后续再去具体实现这个方法。这样不论是后面debug还是更新调整都是会更加方便，可读性也更好地