nru

class NRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}
        self.order = []  # 用于记录访问顺序

    def get(self, key):
        if key in self.cache:
            # 更新访问顺序
            self.order.remove(key)
            self.order.append(key)
            return self.cache[key]
        return -1  # 表示未找到

    def put(self, key, value):
        if key in self.cache:
            # 更新现有项的值和访问顺序
            self.order.remove(key)
        elif len(self.cache) >= self.capacity:
            # 移除最近最少使用的项
            oldest = self.order.pop(0)
            del self.cache[oldest]
        # 添加或更新项
        self.cache[key] = value
        self.order.append(key)

# 使用示例
nru_cache = NRUCache(2)
nru_cache.put(1, 1)
nru_cache.put(2, 2)
print(nru_cache.get(1))  # 返回 1
nru_cache.put(3, 3)       # 该操作会使得密钥 2 作废
print(nru_cache.get(2))  # 返回 -1 (未找到)