设计LRU缓存结构

设计LRU缓存结构_牛客题霸_牛客网

问题简述

设计LRU(最近最少使用)缓存结构。

思路

• 提示：

  • 核心操作：不管什么操作，只要 key 之前存在，都要移除然后重新加入缓存；

  • Python3.6 之后的 dict 就是有序的，所以不需要额外使用其他数据结构；

  • 可以通过 next(iter(dict.keys())) 快速获取最早未使用的 key；

Python

class Solution:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.buf = dict()

    def get(self, key: int) -> int:
        ret = self.buf.get(key, -1)
        if key in self.buf:
            self.buf.pop(key)
            self.buf[key] = ret
        return ret

    def set(self, key: int, value: int) -> None:
        # 这一步很容易忽略，不论 key 是否存在，都应该先 pop，这样重新加入时才可以更新到队尾
        if key in self.buf:
            self.buf.pop(key)
        elif len(self.buf) >= self.capacity:  # key not in self.buf
            tmp = next(iter(self.buf.keys()))
            self.buf.pop(tmp)
        self.buf[key] = value