衡水网站建设服务商,免费详情页模板网站,怎么做应援网站,大宗交易查询平台相关题目#xff1a; 460. LFU 缓存
相关文章 LRU 缓存 – 哈希链表
# 460. LFU 缓存
# Python中和 LinkedHashSet 相似的数据结构 OrderedDict
from collections import OrderedDict
class LFUCache:# key 到 val 的映射#xff0c;我们后文称为 KV 表keyToVal {}# key 到…相关题目 460. LFU 缓存
相关文章 LRU 缓存 – 哈希链表
# 460. LFU 缓存
# Python中和 LinkedHashSet 相似的数据结构 OrderedDict
from collections import OrderedDict
class LFUCache:# key 到 val 的映射我们后文称为 KV 表keyToVal {}# key 到 freq 的映射我们后文称为 KF 表keyToFreq {}# freq 到 key 列表的映射我们后文称为 FK 表freqToKeys {}# 记录最小的频次minFreq 0# 记录 LFU 缓存的最大容量cap 0def __init__(self, capacity: int):self.keyToVal {}self.keyToFreq {}self.freqToKeys {}self.cap capacityself.minFreq 0def get(self, key: int) - int:if key not in self.keyToVal:return -1# 增加 key 对应的 freqself.increaseFreq(key)return self.keyToVal[key]def put(self, key: int, val: int) - None:if self.cap 0:return# 若 key 已存在修改对应的 val 即可if key in self.keyToVal:self.keyToVal[key] val# key 对应的 freq 加一self.increaseFreq(key)return# key 不存在需要插入# 容量已满的话需要淘汰一个 freq 最小的 keyif self.cap len(self.keyToVal):self.removeMinFreqKey()# 插入 key 和 val对应的 freq 为 1# 插入 KV 表self.keyToVal[key] val# 插入 KF 表self.keyToFreq[key] 1# 插入 FK 表self.freqToKeys.setdefault(1, OrderedDict())self.freqToKeys[1].setdefault(key)# 插入新 key 后最小的 freq 肯定是 1self.minFreq 1def removeMinFreqKey(self):# freq 最小的 key 列表keyList self.freqToKeys.get(self.minFreq)# 其中最先被插入的那个 key 就是该被淘汰的 keydeletedKey next(iter(keyList))# 更新 FK 表keyList.pop(deletedKey)if not keyList:self.freqToKeys.pop(self.minFreq)# 问这里需要更新 minFreq 的值吗# 更新 KV 表self.keyToVal.pop(deletedKey)# 更新 KF 表self.keyToFreq.pop(deletedKey)def increaseFreq(self, key: int) - None:freq self.keyToFreq[key]# 更新 KF 表self.keyToFreq[key] freq 1# 更新 FK 表# 将 key 从 freq 对应的列表中删除self.freqToKeys[freq].pop(key)# 将 key 加入 freq 1 对应的列表中self.freqToKeys.setdefault(freq 1, OrderedDict())self.freqToKeys[freq 1].setdefault(key)# 如果 freq 对应的列表空了移除这个 freqif not self.freqToKeys[freq]:del self.freqToKeys[freq]# 如果这个 freq 恰好是 minFreq更新 minFreqif freq self.minFreq:self.minFreq 1
