字节真喜欢问这个算法啊。。。

题目

设计并实现一个满足最近最少使用 (LRU) 缓存约束的数据结构。具体要求如下：

实现 LRUCache 类，包括构造函数 LRUCache(int capacity) 用于初始化缓存的最大容量。
实现 get(int key) 方法，通过键获取值；如果键不存在，则返回 -1。
实现 put(int key, int value) 方法，添加或更新键值对；如果缓存已满，则需要先删除最久未使用的键值对。

函数 get 和 put 必须保证 (O(1)) 的时间复杂度。

题目解析

为了实现一个 LRU 缓存机制，关键在于如何在 (O(1)) 时间复杂度内完成以下操作：

访问缓存项（通过键获取值）
更新缓存项（添加或变更键值对）
维护缓存项的使用顺序，以确保当缓存达到容量限制时，可以快速定位并移除最久未使用的项。

这些需求提示我们需要一个能够快速进行查找操作的数据结构来存储键值对，以及一个能够记录访问顺序的数据结构。哈希表（或字典）非常适合快速查找操作，而双向链表可以有效地维护元素间的顺序关系。因此，LRU 缓存的实现通常结合这两种数据结构：

哈希表存储键与对应节点（包含键、值和指向其他节点的指针）的映射关系，实现 (O(1)) 时间复杂度的查找。
双向链表的每个节点表示一个缓存项，节点间的顺序反映了缓存项的使用顺序。最近访问或更新的节点被移到链表头部，而最久未访问的节点排在链表尾部。这种结构便于在需要时快速移除最久未使用的节点。

设计要点

初始化：构造一个空的双向链表和哈希表，以及设置一个缓存的最大容量。
访问缓存项：通过哈希表快速定位到链表中的节点，然后将其移动到链表头部，表示最近使用。
更新缓存项：如果键存在，更新其值并移动到链表头部；如果键不存在，创建新的节点并添加到链表头部，同时检查缓存容量，必要时移除链表尾部的节点，并从哈希表中删除对应的键。
维护顺序：通过双向链表的插入和删除操作维护缓存项的使用顺序，确保常数时间复杂度内的顺序调整。

参考代码

以下是 LRUCache 类的实现，结合了哈希表和双向链表：

class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}  # 哈希表存储键到节点的映射
        self.head = Node(0, 0)  # 伪头部和伪尾部节点
        self.tail = Node(0, 0)
        self.head.next = self.tail
        self.tail.prev = self.head

    def _add_node(self, node):
        """在链表头部添加一个新节点"""
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def _remove_node(self, node):
        """从链表中移除一个节点"""
        prev = node.prev
       

 next = node.next
        prev.next = next
        next.prev = prev

    def _move_to_head(self, node):
        """将一个节点移动到链表头部"""
        self._remove_node(node)
        self._add_node(node)

    def _pop_tail(self):
        """弹出链表尾部的节点"""
        res = self.tail.prev
        self._remove_node(res)
        return res

    def get(self, key: int) -> int:
        node = self.cache.get(key, None)
        if not node:
            return -1
        self._move_to_head(node)
        return node.value

    def put(self, key: int, value: int):
        node = self.cache.get(key)
        if not node:
            newNode = Node(key, value)
            self.cache[key] = newNode
            self._add_node(newNode)
            if len(self.cache) > self.capacity:
                # 移除链表尾部节点
                tail = self._pop_tail()
                del self.cache[tail.key]
        else:
            node.value = value
            self._move_to_head(node)