LFU Cache,LeetCode,460

好的，我们来详细讨论一下 LeetCode 上的第 460 题：LFU Cache（最不经常使用缓存）。

题目描述

LFU（Least Frequently Used）缓存是一种缓存替换策略，它根据数据访问的频率来淘汰数据。如果一个数据在缓存中很少被访问，那么它将会被优先淘汰。

你需要实现以下功能：

1. LFUCache(int capacity): 用以初始化一个大小为 capacity 的缓存。
2. int get(int key): 如果键 key 存在于缓存中，则返回其值，同时增加该键的使用频率；如果不存在，则返回 -1。
3. void put(int key, int value): 如果键 key 已存在，则更新其值；如果不存在，则插入该键值对。当缓存容量达到上限时，应该淘汰使用频率最低的数据。

示例

LFUCache cache = new LFUCache( 2 / capacity / );

cache.put(1, 1); cache.put(2, 2); cache.get(1); // 返回 1 cache.put(3, 3); // 去除 key 2 cache.get(2); // 返回 -1 (未找到key 2) cache.get(3); // 返回 3 cache.put(4, 4); // 去除 key 1 cache.get(1); // 返回 -1 (未找到 key 1) cache.get(3); // 返回 3 cache.get(4); // 返回 4

解题思路

为了实现 LFU 缓存，我们需要以下几个数据结构：

1. 哈希表 keyToVal：用于存储键到值的映射。
2. 哈希表 keyToFreq：用于存储键到其访问频率的映射。
3. 哈希表 freqToKeys：用于存储频率到具有该频率的所有键的集合的映射。
4. 变量 minFreq：用于记录当前最小的访问频率。

详细实现

初始化

class LFUCache: def init(self, capacity: int): self.capacity = capacity self.keyToVal = {} self.keyToFreq = {} self.freqToKeys = collections.defaultdict(set) self.minFreq = 0

获取值

def get(self, key: int) -> int: if key not in self.keyToVal: return -1

    # 增加该键的使用频率
    old_freq = self.keyToFreq[key]
    self.keyToFreq[key] += 1
    new_freq = self.keyToFreq[key]

    # 更新 freqToKeys
    self.freqToKeys[old_freq].remove(key)
    self.freqToKeys[new_freq].add(key)

    # 如果 old_freq 是最小频率且其对应的集合为空，更新 minFreq
    if not self.freqToKeys[old_freq] and old_freq == self.minFreq:
        self.minFreq += 1

    return self.keyToVal[key]

插入值

def put(self, key: int, value: int) -> None: if self.capacity <= 0: return

    if key in self.keyToVal:
        # 更新值并增加频率
        self.keyToVal[key] = value
        self.get(key)  # 利用 get 方法增加频率
        return

    # 如果缓存已满，需要淘汰一个频率最低的键
    if len(self.keyToVal) >= self.capacity:
        evict_key = next(iter(self.freqToKeys[self.minFreq]))
        self.freqToKeys[self.minFreq].remove(evict_key)
        del self.keyToVal[evict_key]
        del self.keyToFreq[evict_key]

    # 插入新键值对
    self.keyToVal[key] = value
    self.keyToFreq[key] = 1
    self.freqToKeys[1].add(key)
    self.minFreq = 1

总结

LFU 缓存的实现相对复杂，需要维护多个映射关系以确保高效的查找和更新操作。通过使用哈希表和集合，我们能够在 O(1) 的时间复杂度内完成 get 和 put 操作。关键在于合理管理频率信息，并在必要时淘汰最不经常使用的元素。

希望这个详细的解析和代码实现能帮助你理解和解决 LeetCode 上的第 460 题。如果有任何进一步的问题，欢迎继续提问！