力扣 | 460. LFU 缓存

导言

今天的算法打卡题是一道困难题，毫无悬念，没有做出来，可是仍是记录一下自己的思考过程，以及需求去学习和掌握的常识点

标题描绘

过程

剖析

在看完标题描绘之后，我接着便是好好研究了一下它提供的示例：

看完之后，有了大约的思路：

1. 需求两个目标，LFUCacheItem目标表明每个缓存项；LFUCache目标则是用来保护一切缓存项的容器
2. LFUCacheItem目标包含的特点：
   • key：键
   • value：值
   • usageCount：缓存项运用次数计数器
   • lastAccessed： 最终一次访问缓存项的时刻
3. LFUCache目标包含的特点：
   • capacity：缓存的最大容量
   • cache：一个字典，用于将键映射到对应缓存项（LFUCacheItem目标）
4. LFUCache目标包含的办法：
   • get：获取缓存中存在的缓存项的值；缓存项存在回来值，不存在回来 -1
   • put：向缓存中参加缓存项；缓存项存在更新值，不存在创立新值参加
     • 超出缓存容量需求evict最不常运用的缓存项
   • evict：当缓存满了之后，删去最不常运用的缓存项
     • 判别标准：usageCount + lastAccessed
     • 当usageCount相同的情况下，依据lastAccessed决定运用频率

使用

依据上面对标题的剖析之后，完成的代码如下，一比一复刻，便是加了一些关于边界条件的判别：

var LFUCache = function(capacity) {
  this.capacity = capacity;
  this.cache = new Map();
};
var LFUCacheItem = function(key, value, usageCount = 1) {
  this.key = key;
  this.value = value;
  this.usageCount = usageCount;
  this.lastAccessed = performance.now();
}
LFUCache.prototype.get = function(key) {
  if(this.cache.has(key)) {
    const cacheItem = this.cache.get(key);
    cacheItem.usageCount += 1;
    cacheItem.lastAccessed = performance.now();
    return cacheItem.value;
  }
  return -1;
};
LFUCache.prototype.put = function(key, value) {
  if(this.capacity === 0) return;
  if(this.cache.has(key)) {
    const cacheItem = this.cache.get(key);
    cacheItem.usageCount += 1;
    cacheItem.lastAccessed = performance.now();
    cacheItem.value = value;
    return;
  }
  if(this.cache.size >= this.capacity) {
    this.evict();
  }
  this.cache.set(key, new LFUCacheItem(key, value));
};
LFUCache.prototype.evict = function() {
  const minFrequency  = new LFUCacheItem(0, 0, Infinity);
  this.cache.forEach((cacheItem) => {
    if(cacheItem.usageCount < minFrequency.usageCount) {
      minFrequency.key = cacheItem.key;
      minFrequency.usageCount = cacheItem.usageCount;
      minFrequency.lastAccessed = cacheItem.lastAccessed;
    } else if(cacheItem.usageCount == minFrequency.usageCount) {
      if(cacheItem.lastAccessed < minFrequency.lastAccessed) {
        minFrequency.key = cacheItem.key;
        minFrequency.usageCount = cacheItem.usageCount;
        minFrequency.lastAccessed = cacheItem.lastAccessed;
      }
    }
  })
  this.cache.delete(minFrequency.key);
}

成果

在提交后，发现最终几个测试用例超出时刻约束了，然后回来标题描绘检查，的确，有说到get和put办法的平均时刻复杂度要为O(1)

回来检查代码会发现，get办法是没有问题的，主要是put办法，在参加缓存项时需求依据缓存容量和当前缓存size来决定是否需求evict不经常运用的缓存项，而我之前完成evict办法时是经过遍历一切缓存项并依据evict标准去删去不经常运用的缓存项，这归于暴力处理的办法，时刻复杂度是O(n)，不符合标题要求，因此会超时

再剖析

依据上面成果已经推测出是evict办法的问题，要使evict删去不经常用的缓存项的时刻复杂度为O(1)，那便是不需求for循环遍历这步操作，要是缓存目标LFUCache本身就实时保护了minFrequency变量，用来实时保护运用频率最低的缓存项，那么在evict办法里便能够直接删去即可

现在问题便是：如何完成实时保护minFrequency变量？

羞愧，我在尝试了一番后，仍是没能完成，实在是超出能力范围了，看了一下题解，有说到的办法：

• 哈希表
• 双向链表
• 红黑树
• 单调栈
• ……

结论

关于LFU 缓存这个打卡题，目前我是打不成功了，记录下来思路与需求去了解的常识，在掌握这些常识的某一天，再次来打卡~