题目

题目来源:力扣(LeetCode)

设计和构建一个“最近最少使用”缓存,该缓存会删除最近最少使用的项目。缓存应该从键映射到值(允许你插入和检索特定键对应的值),并在初始化时指定最大容量。当缓存被填满时,它应该删除最近最少使用的项目。
它应该支持以下操作: 获取数据 get 和 写入数据 put 。

获取数据 get(key) - 如果密钥 (key) 存在于缓存中,则获取密钥的值(总是正数),否则返回 -1。
写入数据 put(key, value) - 如果密钥不存在,则写入其数据值。当缓存容量达到上限时,它应该在写入新数据之前删除最近最少使用的数据值,从而为新的数据值留出空间。

示例:

LRUCache cache = new LRUCache( 2 / 缓存容量 / );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 该操作会使得密钥 2 作废
cache.get(2); // 返回 -1 (未找到)
cache.put(4, 4); // 该操作会使得密钥 1 作废
cache.get(1); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.get(4); // 返回 4

思路分析

LRU 是一种十分常见的页面置换算法。
将 LRU 翻译成大白话就是:当不得不淘汰某些数据时(通常是容量已满),选择最久未被使用的数据进行淘汰。

题目让我们实现一个容量固定的 LRUCache 。如果插入数据时,发现容器已满时,则先按照 LRU 规则淘汰一个数据,再将新数据插入,其中「插入」和「查询」都算作一次“使用”。

可以通过 🌰 来理解,假设我们有容量为 22 的 LRUCache 和 测试键值对 [1-1,2-2,3-3] ,将其按照顺序进行插入 & 查询:

插入 1-1,此时最新的使用数据为 1-1
插入 2-2,此时最新使用数据变为 2-2
查询 1-1,此时最新使用数据为 1-1
插入 3-3,由于容器已经达到容量,需要先淘汰已有数据才能插入,这时候会淘汰 2-2,3-3 成为最新使用数据
键值对存储方面,我们可以使用「哈希表」来确保插入和查询的复杂度为 O(1)O(1)。

另外我们还需要额外维护一个「使用顺序」序列。

我们期望当「新数据被插入」或「发生键值对查询」时,能够将当前键值对放到序列头部,这样当触发 LRU 淘汰时,只需要从序列尾部进行数据删除即可。

具体地:

  1. LRU的缓存策略就像是维护一个队列,每次把访问的节点移动过到队列的末尾,当队列的长度 大于缓存的长度,就把队列首部的元素给删除。
  2. 在调用get和put的时候,访问或者修改了的数据要被更新到最新访问的位置,所以会在这里处理数据 的顺序。
  3. 其次存取的数据要能记录访问顺序,或者说要有序。
  1. /**
  2. * @param {number} capacity
  3. */
  4. var LRUCache = function(capacity) {
  5. // 最大缓存容量
  6. this.capacity = parseInt(capacity, 10);
  7. // 数据缓存对象
  8. this.cache = {};
  9. // 键名缓存数组,还可提供 key 的访问时间顺序
  10. this.keys = [];
  11. };
  12. /**
  13. * @param {number} key
  14. * @return {number}
  15. */
  16. LRUCache.prototype.get = function(key) {
  17. const idx = this.keys.indexOf(key);
  18. if (idx === -1) {
  19. return -1;
  20. }
  21. // 更新 keys 的顺序
  22. this.keys.push(this.keys.splice(idx, 1)[0]);
  23. return this.cache[key];
  24. };
  25. /**
  26. * @param {number} key
  27. * @param {number} value
  28. * @return {void}
  29. */
  30. LRUCache.prototype.put = function(key, value) {
  31. const idx = this.keys.indexOf(key);
  32. if (idx !== -1) {
  33. // 更新原有数据和访问时间顺序
  34. this.keys.push(this.keys.splice(idx, 1)[0]);
  35. } else {
  36. if (this.keys.length === this.capacity) {
  37. // 超出缓存容量,删除缓存中最少使用的缓存
  38. this.cache[this.keys.shift()] = null;
  39. }
  40. this.keys.push(key);
  41. }
  42. this.cache[key] = value;
  43. };