[146] LRU 缓存

请你设计并实现一个满足  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

提示：

1 <= capacity <= 3000

0 <= key <= 10000

0 <= value <= 10^5

最多调用 2> 10^5 次 get 和 put

本题要求我们设计了一个 LRU 缓存的数据结构。所谓 LRU，就是指因缓存容量有限，因此仅缓存最近最常访问的数据，超出容量后最久未被访问的数据会被丢弃。在程序设计中，尤其是后端的缓存设计中十分常用。

借助 ES6 的 Map 特性，我们既拥有了存取记录有序，又拥有了存取复杂度都为 O(1) 的数据结构。

于是很容易写出该题的设计。

class LRUCache {
  cache: Map<number, number>;
  capacity: number;
  constructor(capacity: number) {
    this.capacity = capacity;
    this.cache = new Map<number, number>();
  }

  get(key: number): number {
    // 若未匹配值，则返回 -1
    if (!this.cache.has(key)) {
      return -1;
    }

    const value = this.cache.get(key);
    // 由于进行了一次查询，更新 LRU 列表到队尾
    this.cache.delete(key);
    this.cache.set(key, value);

    return value;
  }

  put(key: number, value: number): void {
    // 若 LRU 中已经存在 key，则需要先进行删除
    if (this.cache.has(key)) {
      this.cache.delete(key);
    }
    this.cache.set(key, value);

    // 若超出 LRU 队列长度，删去队头最久未被访问的记录
    if (this.cache.size > this.capacity) {
      // map.keys() 返回一个迭代器，迭代器调用 next() 方法，返回下一个值到 value 中
      // 即表示获取 map 的第一个 key
      const firstKey = this.cache.keys().next().value;
      this.cache.delete(firstKey);
    }
  }
}