笔记1

146.LRU 缓存：https://leetcode.cn/problems/lru-cache/

请你设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构。

实现 LRUCache 类：

LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该逐出最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

示例：

输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

解决思路

要实现一个满足LRU缓存约束的数据结构，我们需要综合使用哈希表和双向链表。双向链表用于表示缓存中的数据项之间的顺序，其中最近访问（包括读取和写入）的元素被放置在链表的头部，而最久未使用的元素则被放置在链表的尾部。哈希表则用于存储键与其在双向链表中对应节点的引用，使得我们能够以O(1)的时间复杂度找到任意键值。

解决步骤

1. 定义双向链表节点

首先，定义双向链表的节点类，该节点类需要含有key, value, prev, 和next四个属性。key和value存储键值对信息，prev和next指向前一个节点和后一个节点。

2. 初始化LRUCache

初始化一个哈希表，用来存储键和其对应节点（双向链表中的位置）之间的映射。
创建两个特殊的双向链表节点head和tail，分别作为哨兵节点标记链表的开始和结束。这样，实际存储的缓存数据位于这两个节点之间。
设置一个变量capacity来存储缓存的容量限制。
设置一个变量size来跟踪当前缓存大小。

3. 实现get方法

在哈希表中查找给定的key。
如果key存在，将其对应的节点移动到链表头部，并返回节点的value。
如果key不存在，返回-1。

4. 实现put方法

检查key是否已经存在：
如果加入新节点后超出了容量capacity，则删除链表尾部的节点，并从哈希表中移除对应的key。
如果存在，则更新其value，并将该节点移至链表头部。
如果不存在，创建一个新的节点，并将其加入到链表头部以及哈希表中。

5. 移动节点到链表头部操作

将目标节点从链表中摘除。
将摘除的节点插入到链表头部（即head节点之后）。

6. 删除链表尾部操作

找到链表尾部的节点（tail节点的前一个节点）。
从链表中删除该节点，并确保前一个节点和tail节点正确连接。
同时，从哈希表中删除该节点的key。

通过以上步骤，可以确保实现的LRU缓存既能满足时间复杂度为O(1)的访问与更新需求，也能正确地按照最近最少使用原则管理缓存内容。

下面给出了分别使用Python和Java实现的LRU缓存机制的代码~

Python 实现

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

class LRUCache:
    def __init__(self, capacity: int):
        self.cache = {}  # 哈希表，用于快速定位节点
        self.head = DLinkedNode()  # 虚拟头节点
        self.tail = DLinkedNode()  # 虚拟尾节点
        self.head.next = self.tail
        self.tail.prev = self.head
        self.capacity = capacity
        self.size = 0

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        node = self.cache[key]  # 定位到哈希表中的节点
        self.moveToHead(node)  # 移动到链表头部
        return node.value

    def put(self, key: int, value: int) -> None:
        if key not in self.cache:
            node = DLinkedNode(key, value)
            self.cache[key] = node
            self.addToHead(node)
            self.size += 1
            if self.size > self.capacity:
                removed = self.removeTail()
                self.cache.pop(removed.key)
                self.size -= 1
        else:
            node = self.cache[key]
            node.value = value
            self.moveToHead(node)

    def addToHead(self, node):
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def removeNode(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def moveToHead(self, node):
        self.removeNode(node)
        self.addToHead(node)

    def removeTail(self):
        node = self.tail.prev
        self.removeNode(node)
        return node

# 测试代码
if __name__ == "__main__":
    lRUCache = LRUCache(2)
    lRUCache.put(1, 1)  # 缓存是 {1=1}
    lRUCache.put(2, 2)  # 缓存是 {1=1, 2=2}
    print(lRUCache.get(1))  # 返回 1
    lRUCache.put(3, 3)    # 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
    print(lRUCache.get(2))  # 返回 -1 (未找到)
    lRUCache.put(4, 4)    # 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
    print(lRUCache.get(1))  # 返回 -1 (未找到)
    print(lRUCache.get(3))  # 返回 3
    print(lRUCache.get(4))  # 返回 4