LRU缓存

Leetcode Link: 146. LRU 缓存 - 力扣（LeetCode）

题目

请你设计并实现一个满足 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) 的平均时间复杂度运行。

解法一

思路：看到题目要我们实现一个可以存储 key-value 形式数据的数据结构，并且可以记录最近访问的 key 值。首先想到的就是用字典来存储 key-value 结构，这样对于查找操作时间复杂度就是 O(1)。

但是因为字典本身是无序的，所以我们还需要一个类似于队列的结构来记录访问的先后顺序，这个队列需要支持如下几种操作：

在末尾加入一项
去除最前端一项
将队列中某一项移到末尾

首先考虑列表结构。 对于列表加入有 append()，删除有 pop() 操作，这两个都是 O(1) 的时间复杂度。而对于将队列中某一项移到末尾，因为列表中存储的是哈希表的 key，考虑这样一种情况：

# 操作
cache = LRUCache(4)
cache.put(3, 2)
cache.put(2, 1)
cache.put(1, 1)
# 操作之后队列：
# queue = [3, 2, 1]

此时我们再进行 cache.put(2, 2) 的操作，因为2已经存在在哈希表中，这说明队列中已经存在值为2的元素，那么问题来了，如何在常数时间内把它挑出来移到队尾呢？

答案是不行，所以用列表无法实现常数时间复杂度。

之后再考虑单链表。

对于单链表，哈希表的结构类似于 {key: ListNode(value)}，即键所对应的是一个节点地址，节点的值是 value。对于链表，遇到上面那种情况时可以在常数的时间内找到对应的节点，但是如果想将它移到尾部则需要从头遍历到该节点才能保证链表不断，对于这种情况需要的时间复杂度也是O(n)

为了解决移到末尾这个问题，需要使用双链表来记录，结构大概如下图所示： |600

题解：

class Node:
    def __init__(self, key = None, val=0, pre=None, next=None):
        self.val = val
        self.pre = pre
        self.key = key
        self.next = next
 
class LRUCache:
 
    def __init__(self, capacity: int):
        self.n = capacity
        self.dict = {}
        self.dummy_head = Node()
        self.dummy_tail = Node(pre=self.dummy_head)
        self.dummy_head.next = self.dummy_tail
 
	# 头部是最近用的
	# 这里不能传入dict[key] !! 即不能传入node
    def move_to_head(self, key):  
        # 断开连接并接上两边
        self.dict[key].pre.next = self.dict[key].next
        self.dict[key].next.pre = self.dict[key].pre
        # 移动到头部
        self.dict[key].pre = self.dummy_head
        self.dict[key].next = self.dummy_head.next
        self.dummy_head.next.pre = self.dict[key]
        self.dummy_head.next = self.dict[key]
 
    def get(self, key: int) -> int:
        if key in self.dict.keys():
	        # 这里get之后一定要移动到头部，我开始就没做
            self.move_to_head(key) 
            return self.dict[key].val
        else:
            return -1
 
    def put(self, key: int, value: int) -> None:
        if key in self.dict.keys():
            self.dict[key].val = value
            # 存在，把这个需要移动到第一顺位
            self.move_to_head(key)
 
        else: # 不存在
            if len(self.dict) < self.n:
                new = Node(key = key, val = value)
                self.dict[key] = new
                # 添加到第一顺位，头部
                new.pre = self.dummy_head
                new.next = self.dummy_head.next
                self.dummy_head.next.pre = new
                self.dummy_head.next = new
            elif len(self.dict) == self.n:
                new = Node(key = key, val = value)
                self.dict[key] = new
                # 添加到第一顺位，头部
                new.next = self.dummy_head.next
                new.pre = self.dummy_head
                self.dummy_head.next.pre = new
                self.dummy_head.next = new
                # 去掉最后一个
                del_key = self.dummy_tail.pre.key
                self.dict.pop(del_key)
                self.dummy_tail.pre.pre.next = self.dummy_tail
                self.dummy_tail.pre = self.dummy_tail.pre.pre

启发和联系

错误分析由于题目要求”函数 get 和 put 必须以 O(1) 的平均时间复杂度运行”，我就不知道怎么做了。

若不考虑这个要求，则可以使用

一个字典进行 key-value 查询
一个最长为 capacity 的 list 来保存有效的 key，来了一个新的 key，先在 list 里查询是不是有效的，在去字典中找 value
- 若有效，在去字典中找 value
- 若无效，则返回-1
- 若需要添加新的值，先看是不是在 list 里，若在，则需要把 list 的值提到最开始，然后在更新；若不在 list 里，则需要 leftpop 出最久没用的，然后 append 这个新的。

然而该方法的时间复杂度不满足要求。

My Obsidian Blog

探索

LRU缓存

题目

解法一

启发和联系

关系图谱

目录