设计一个简单的 LRU 缓存。

Question

设计一个简单的 LRU 缓存。

Accepted Answer

LRU（Least Recently Used）缓存是一种常用的缓存淘汰策略，当缓存满时，会优先淘汰最近最少使用的数据。可以使用 Python 的 OrderedDict 来实现一个简单的 LRU 缓存。OrderedDict 是一个有序的字典，它可以记住元素插入的顺序。具体实现步骤如下：首先，初始化一个 OrderedDict 作为缓存，并设置缓存的容量。当进行 get 操作时，如果键存在于缓存中，将该键值对移动到 OrderedDict 的末尾，表示最近使用；如果键不存在，返回 -1。当进行 put 操作时，如果键已经存在，更新该键的值，并将其移动到 OrderedDict 的末尾；如果键不存在，需要判断缓存是否已满，如果已满，删除 OrderedDict 的第一个元素（即最近最少使用的元素），然后插入新的键值对。以下是实现代码：
python
from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = OrderedDict()

def get(self, key: int) -> int:
        if key in self.cache:
            self.cache.move_to_end(key)
            return self.cache[key]
        return -1

def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)

这样就实现了一个简单的 LRU 缓存。