NC93.设计LRU缓存

题目描述:

设计LRU(最近最少使用)缓存结构，该结构在构造时确定大小，假设大小为 capacity ，操作次数是 n ，并有如下功能:

• 1. Solution(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
• 2. get(key)：如果关键字 key 存在于缓存中，则返回key对应的value值，否则返回 -1 。
• 3. set(key, value)：将记录(key, value)插入该结构，如果关键字 key 已经存在，则变更其数据值 value，如果不存在，则向缓存中插入该组 key-value ，如果key-value的数量超过capacity，弹出最久未使用的key-value

提示：

• 1.某个key的set或get操作一旦发生，则认为这个key的记录成了最常使用的，然后都会刷新缓存。
• 2.当缓存的大小超过capacity时，移除最不经常使用的记录。
• 3.返回的value都以字符串形式表达，如果是set，则会输出"null"来表示(不需要用户返回，系统会自动输出)，方便观察
• 4.函数set和get必须以O(1)的方式运行
• 5.为了方便区分缓存里key与value，下面说明的缓存里key用""号包裹

示例1：

输入：
["set","set","get","set","get","set","get","get","get"],
[[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]],
2

返回值：
["null","null","1","null","-1","null","-1","3","4"]

说明：
我们将缓存看成一个队列，最后一个参数为2代表capacity

Solution s = new Solution(2);
s.set(1,1); //将(1,1)插入缓存，缓存是{"1"=1}，set操作返回"null"
s.set(2,2); //将(2,2)插入缓存，缓存是{"2"=2，"1"=1}，set操作返回"null"
output=s.get(1);// 因为get(1)操作，缓存更新，缓存是{"1"=1，"2"=2}，get操作返回"1"
s.set(3,3); //将(3,3)插入缓存，缓存容量是2，故去掉某尾的key-value，缓存是{"3"=3，"1"=1}，set操作返回"null" 
output=s.get(2);// 因为get(2)操作，不存在对应的key，故get操作返回"-1"
s.set(4,4); //将(4,4)插入缓存，缓存容量是2，故去掉某尾的key-value，缓存是{"4"=4，"3"=3}，set操作返回"null" 
output=s.get(1);// 因为get(1)操作，不存在对应的key，故get操作返回"-1"
output=s.get(3);//因为get(3)操作，缓存更新，缓存是{"3"=3，"4"=4}，get操作返回"3"
output=s.get(4);//因为get(4)操作，缓存更新，缓存是{"4"=4，"3"=3}，get操作返回"4"

这道题目有两个点需要注意，在二维数组中，子数组如果第一个元素是1，例如 [1,1,1], 这种代表的是set操作, 数组中的第二个元素和第三个元素分别代表的是key和value。

所以[1,1,1]代表的操作是set(1,1), 对于[2,1]来说，第一个2表示取值操作，要get(1)，返回是[1]，因为执行了get(1)操作，缓存会更新，缓存变成了 {"2"=2,"3"=2,"1"=1} 这个说明非常有意思，取值操作结束后，最新取到的值的会放在最后面。下次再进行操作的时候，会将最新的key也是放在最后。

总结一句话，最新取值操作的key放在最后，最新set的key也放在最后，如果塞值的时候发现空间不够了，这个时候应该做的就是将开头的值去除掉。

取值和塞值，我们应该使用一个map来作为映射表。缓存的顺序，我们使用一个数组来维持这个顺序。

具体实现逻辑是，

• 环遍历二维数组, 通过判断子数组的第一个数字是1还是2 做分流操作。
• 如果是 1 代表的是set操作，set操作的时候，将所有的映射关系全部放入map中，同时需要维护缓存队列。
• 如果是 2 代表的是取出缓存的操作，取值操作时候，分为能够取到和取不到两种情况。如果能够取到需要更新key在缓存队列中的位置。

本质上借助map和队列这种数据结构。

/**
 * lru design
 * @param operators int整型二维数组 the ops
 * @param k int整型 the k
 * @return int整型一维数组
 */
function LRU( operators ,  k ) {
  let map = new Map(); // 存放数字之间的映射
  let res = [] // 存放操作结果的数组
  let list = [] // 缓存队列

  // 对数组使用for in 循环, 返回的 item 是数组的索引
  for(let item in operators) {
    let op = operators[item][0]; // 每个数组的第一项是操作方式
    if(op === 1 ) { // 代表的是存值操作
      // 存入map中，map 中保存着所有关系的映射
      map.set(operators[item][1],operators[item][2])
      // 在存值操作时候如果发现已经超出队列的容量
      if(list.length >= k) {
        // 将缓存队列的队尾删除，这个是使用频率最少的
        list.shift();
      }
      // 将新的值放入队头
      list.push(operators[item][1])
    } else if(op === 2) { // 代表的是取值操作
      let key = operators[item][1];
      // 判断key在缓存队列中是否存在
      let index = list.indexOf(key); 
      
      if(index === -1)  { // 说明不存在
        res.push(-1)
      } else { // 如果在缓存队列中存在
        res.push(map.get(key)) // 存放的是value
        list.splice(index,1) // 更新当前的这个key到队列的队头
        list.push(key)
      }
    }
  }
  return res
}

题目更新：牛客网上对这道题目做了修改

描述

设计LRU(最近最少使用)缓存结构，该结构在构造时确定大小，假设大小为 capacity ，操作次数是 n ，并有如下功能:

• 1. Solution(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
• 2. get(key)：如果关键字 key 存在于缓存中，则返回key对应的value值，否则返回 -1 。
• 3. set(key, value)：将记录(key, value)插入该结构，如果关键字 key 已经存在，则变更其数据值 value，如果不存在，则向缓存中插入该组 key-value ，如果key-value的数量超过capacity，弹出最久未使用的key-value

入参: ["set","set","get","set","get","set","get","get","get"],[[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]],2

新的入参中是三个入参 操作 操作的数据，容器大小。

/**
 * @param {number} capacity
 */
var Solution = function(capacity) {
  this.max = capacity;
  // 这是map集合
  this.map = new Map();
};

/** 
 * @param {number} key
 * @return {number}
 */
Solution.prototype.get = function(key) {
  // 如果集合中包含这个值，想办法返回这个值
  if (this.map.has(key)) {
    // 获取当前这个key对应的值
    let value = this.map.get(key)
    // 先删除这个值
    this.map.delete(key)
    // 然后把这个值重新放入map中，更新缓存顺序
    this.map.set(key,value)
    return value
  } else {
    return -1
  }
};

/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
Solution.prototype.set = function(key, value) {
  if (this.map.has(key)) {
    this.map.delete(key);//为了将最近使用过的放在最后面
  }
  
  this.map.set(key, value);
  
  if (this.map.size > this.max) {//超过容量
    // this.map.delete(Array.from(this.map.keys())[0]) // 这样也可以
    this.map.delete(this.map.keys().next().value);//得到最前面的key并删除此键值对
  }
};

module.exports = {
  Solution : Solution
};

/**
 * Your Solution object will be instantiated and called as such:
 * var solution = new Solution(capacity)
 * var output = solution.get(key)
 * solution.set(key,value)
 */

1216 更新记录

• 今天学习的时候，尝试使用了 debug 模式。

20220705 更新记录

• 今天早上来公司第一件事情就是写这道题目，但是提交的时候却报错了，原因是get方法中没有写返回值

20220916 更新记录

• 不要被题目带歪了，我们正常情况下，维护的就是map的最后一个结构是最新的，第一个位置的元素是旧的。