LRU Cache 力扣题解

题目描述

题目链接: 146. LRU 缓存机制

设计并实现一个 LRU (Least Recently Used) 缓存机制，它支持 get 和 put 操作。

函数签名：

int get(int key)：如果密钥 key 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
void put(int key, int value)：如果密钥不存在，请写入数据。当缓存容量达到上限时，在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

进阶：是否可以在 O(1) 时间复杂度内完成这两种操作？

解题思路

LRUCache 的核心需求：

快速查找：get 操作需要 O(1) 时间复杂度
快速删除和插入：put 操作需要 O(1) 时间复杂度
维护访问顺序：记录最近使用和最久未使用的元素

数据结构选择：

哈希表（字典）：提供 O(1) 的查找速度
双向链表：维护元素的访问顺序，支持 O(1) 的插入和删除

设计思想：

双向链表从头到尾按照最近访问时间排序，尾部是最久未使用的元素
哈希表存储 key 到链表节点的映射
get 操作时，将访问的节点移动到链表头部
put 操作时：
- 如果 key 已存在，更新 value 并移动到头部
- 如果 key 不存在，创建新节点放到头部
- 如果容量已满，删除尾部节点（最久未使用），并删除哈希表中对应项

代码实现

Python 实现

class ListNode:
    def __init__(self, key=None, value=None):
        self.key = key
        self.value = value
        self.prev = None
        self.next = 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.prev = self.head

    def move_node_to_tail(self, key):
        node = self.hashmap[key]
        node.prev.next = node.next
        node.next.prev = node.prev

        node.prev = self.tail.prev
        node.next = self.tail

        self.tail.prev.next = node
        self.tail.prev = node

    def get(self, key: int) -> int:
        if key in self.hashmap:
            self.move_node_to_tail(key)
        res = self.hashmap.get(key, -1)
        if res == -1:
            return res
        else:
            return res.value

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

            new = ListNode(key, value)
            self.hashmap[key] = new
            new.prev = self.tail.prev
            new.next = self.tail
            self.tail.prev.next = new
            self.tail.prev = new


# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)