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) 的平均时间复杂度运行。

测试用例：

// 输入
const handle = ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"];
const arr = [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]];
// 输出
const output = [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
**/

解题思路

LRU 缓存的核心思想是：当缓存空间不足时，优先移除最久未使用的数据。为了实现这一目标，我们需要：

快速查找：通过 key 快速找到对应的值。
维护访问顺序：记录每个 key 的访问顺序，确保最近访问的 key 排在前面，最久未访问的 key 排在后面。

在 JavaScript 中，Map 数据结构非常适合实现 LRU 缓存，因为：

Map 的键值对是有序的，插入顺序即访问顺序。
Map 提供了 O(1) 时间复杂度的查找、插入和删除操作。

代码实现

/**
 * @param {number} capacity
 */
var LRUCache = function(capacity) {
  this.maxSize = capacity; // 缓存的最大容量
  this.map = new Map();    // 使用 Map 存储键值对
};
 
/** 
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function(key) {
  if (!this.map.has(key)) return -1; // 如果 key 不存在，返回 -1
  const value = this.map.get(key);   // 获取 key 对应的值
  this.map.delete(key);              // 删除旧的键值对
  this.map.set(key, value);          // 重新插入，更新访问顺序
  return value;                      // 返回值
};
 
/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function(key, value) {
  if (this.map.has(key)) this.map.delete(key); // 如果 key 已存在，先删除
  this.map.set(key, value);                   // 插入新的键值对
  if (this.map.size > this.maxSize) {          // 如果超出容量
    const firstKey = this.map.keys().next().value; // 获取最久未使用的 key
    this.map.delete(firstKey);               // 删除最久未使用的键值对
  }
};
 
/**
 * Your LRUCache object will be instantiated and called as such:
 * var obj = new LRUCache(capacity)
 * var param_1 = obj.get(key)
 * obj.put(key,value)
 */

代码解析

构造函数 LRUCache：
- 初始化缓存的最大容量 maxSize。
- 使用 Map 存储键值对。
get 方法：
- 如果 key 不存在，返回 -1。
- 如果 key 存在，获取其值，并更新访问顺序：
  - 先删除旧的键值对。
  - 再重新插入，确保该 key 位于 Map 的末尾（表示最近使用）。
put 方法：
- 如果 key 已存在，先删除旧的键值对。
- 插入新的键值对。
- 如果缓存大小超过 maxSize，删除 Map 中的第一个键值对（最久未使用）。

复杂度分析

时间复杂度：
- get 和 put 操作的时间复杂度均为 O(1)，因为 Map 的查找、插入和删除操作都是 O(1)。
空间复杂度：
- 空间复杂度为 O(capacity)，因为缓存最多存储 capacity 个键值对。

总结

通过使用 Map 数据结构，我们可以高效地实现 LRU 缓存机制。Map 的有序性使得维护访问顺序变得非常简单，而 O(1) 的操作复杂度确保了缓存的性能。这道题是经典的数据结构设计题，掌握 LRU 缓存的实现对于理解缓存机制和算法设计非常有帮助。

ES6+TS

class LRUCache {
    #map // #就是私有变量，外界无法访问
    #length
    constructor(capacity: number) {
      this.#length = capacity;
      this.#map = new Map();
    }
 
    get(key: number): number {
      if(!this.#map.has(key)) return -1;
      const value = this.#map.get(key);
      this.#map.delete(key);
      this.put(key, value);
      return value;
    }
 
    put(key: number, value: number): void {
      if(this.#map.has(key)){
        this.#map.delete(key);
      }
      this.#map.set(key, value);
      if(this.#map.size > this.#length) {
        this.#map.delete(this.#map.keys().next().value)
      }
    }
}
 
/**
 * Your LRUCache object will be instantiated and called as such:
 * var obj = new LRUCache(capacity)
 * var param_1 = obj.get(key)
 * obj.put(key,value)
 */

Dong 的笔记

探索