回答

无

分析

标准实现：使用双向链表+Map的组合

见参考资料。

JS 特有的简单实现，利用 Map 中 key 的有序性

  1. // JS特有的最简单实现，利用Map中key的有序性
  2. class LRUCache {
  3.   constructor(capacity: number) {
  4.     this.capacity = capacity;
  5.     this.dataMap = new Map();
  6.   }
  8.   // 数据存储，使用map，并且利用到map中key的有序性
  9.   dataMap: Map<any, any> = new Map();
  11.   // 缓存个数
  12.   capacity: number;
  14.   // 时间复杂度：O(1)
  15.   // 有额外的空间损失
  16.   get(key: any) {
  17.     // 仅在有此key的时候重写
  18.     if (this.dataMap.has(key)) {
  19.       // get算作使用一次，利用map中key的有序特性，重写一次key，则将key置于map的最后
  20.       let result = this.dataMap.get(key);
  21.       this.dataMap.delete(key);
  22.       this.dataMap.set(result, key);
  23.       return result;
  24.     }
  25.   }
  27.   // 时间复杂度：O(n)，因为Map.keys()在底层需要遍历，虽然实现起来挺快的
  28.   put(key: any, value: any) {
  29.     // 检查是否已满
  30.     if (this.dataMap.size >= this.capacity) {
  31.       let deleteKey = [...this.dataMap.keys()][0];
  32.       this.dataMap.delete(deleteKey);
  33.     }
  34.     // 放入
  35.     this.dataMap.set(key, value);
  36.   }
  37. }
  39. // test
  40. const cache = new LRUCache(2);
  41. cache.put(1, "a");
  42. cache.put(2, "b");
  43. console.log(cache.get(1)); // return 'a'
  44. cache.put(3, "c"); // remove 2 from cache
  45. console.log(cache.get(2)); // return null

参考资料

  1. 每周算法-缓存置换算法 [https://juejin.im/post/6844903928945967111]