LeetCode 460. LFU 缓存 题目描述 请你设计并实现一个满足 LFU（最近最少使用）缓存约束的数据结构。 实现 LFUCache 类： LFUCache(int capacity) 用数据结构的容量 capacity 初始化对象。 int get(int key) 如果键 key 存在于缓存中，则获取键的值，否则返回 -1 。 void put(int key, int value) 如果键 key 已存在，则变更其值；如果键不存在，请插入键值对。当缓存达到其容量 capacity 时，则应该在插入新项之前，移除最不常用的项。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该移除最近最久未使用的键。 「使用频率」是指自该项被插入后对其调用 get 和 put 函数的次数。调用次数会随着时间推移而增加。 解题过程 这个问题的核心在于，淘汰策略有两个维度： 使用频率（Frequency） 和 使用时间（Recency） 。当需要淘汰时，先淘汰使用频率最低的项。如果有多项频率相同，则在这些频率相同的项中，淘汰最久未被访问（get或put）的项。 核心数据结构分析 为了高效地实现 get 和 put 操作（理想情况下时间复杂度为 O(1)），我们需要设计一组巧妙的数据结构来维护信息。 key 到 (value, frequency) 的映射（ keyToValFreq ）：这样我们可以通过 key 在 O(1) 时间内获取到对应的值和当前的使用频率。 我们需要按频率组织数据。一个自然的想法是，为每个频率维护一个链表，链表中的节点按访问时间排序，最近访问的放在头部，最久未访问的放在尾部。这样，同一个链表内的节点频率相同，并且天然保持了访问时序。 我们需要一个 频率 到 对应链表 的映射（ freqToKeys ）。 为了快速找到最小频率，我们需要一个变量 minFreq 来记录当前缓存中的所有键的最低使用频率。当淘汰发生时，我们直接去 minFreq 对应的链表中删除尾部的节点（最久未使用的）即可。 数据结构定义 keyToNode: Map<key, Node> ：一个哈希表，用于通过 key 快速找到对应的节点。节点 Node 包含 key , value , frequency 。 freqToDList: Map<frequency, DoublyLinkedList> ：一个哈希表，用于通过 频率 快速找到对应的双向链表。每个双向链表 DoublyLinkedList 存储具有相同频率的节点，链表头部是最近访问的节点，尾部是最久未访问的节点。 minFreq: int ：当前所有键中的最小使用频率。 capacity: int ：缓存容量。 get(key) 操作详解 检查存在性 ：如果 key 不存在于 keyToNode 中，直接返回 -1 。 增加频率 ：如果 key 存在，我们找到了对应的节点 node 。 记录节点旧的频率 oldFreq = node.freq 。 将节点的频率加一： node.freq++ 。 更新链表 ： 将节点 node 从旧的频率链表 freqToDList[oldFreq] 中移除。 将节点 node 添加到新的频率链表 freqToDList[oldFreq + 1] 的头部。 更新 minFreq（关键且易错） ： 如果旧的频率 oldFreq 正好等于当前的 minFreq ， 并且 旧的频率链表 freqToDList[oldFreq] 在移除节点 node 后变为空，这意味着缓存中已经没有任何一个键的使用频率是 oldFreq 了。那么，我们就需要将 minFreq 增加 1（因为原来的最低频率链表现在空了，下一个更高的频率 oldFreq+1 成为了新的最低频率）。 如果旧的频率链表在移除节点后不为空，或者 oldFreq 不等于 minFreq ，则 minFreq 保持不变。 返回值 ：返回节点 node 的值。 put(key, value) 操作详解 特殊情况 ：如果 capacity 为 0，直接返回，无法插入。 更新已存在键 ：如果 key 已经存在于 keyToNode 中。 更新节点的值。 然后， 执行一次 get(key) 操作 。这是因为 put 操作也视为一次访问，会增加该键的使用频率。而 get 操作中的逻辑（增加频率、更新链表、更新 minFreq ）完全适用于这里。这样可以避免代码重复。 插入新键（核心淘汰逻辑） ：如果 key 不存在。 检查容量 ：如果当前缓存已满（即 keyToNode.size() == capacity ），需要执行淘汰。 找到淘汰候选 ：最低频率 minFreq 对应的双向链表 freqToDList[minFreq] 的尾部节点，就是即将被淘汰的节点（它是所有最低频率节点中最久未被访问的）。 执行淘汰 ： 从 freqToDList[minFreq] 中移除尾部节点。 根据尾部节点的 key ，从 keyToNode 中删除对应的映射。 创建新节点 ：创建一个新的节点， key 和 value 为传入值，频率 frequency 初始化为 1（因为这是第一次访问）。 更新数据结构 ： 将新节点加入 keyToNode 。 将新节点加入到频率为 1 的双向链表 freqToDList[1] 的头部（如果频率 1 的链表不存在，则先创建）。 重置 minFreq ：因为新插入的节点频率是 1，这一定是整个缓存中最低的频率。所以，无论之前的 minFreq 是多少，现在都必须设置为 1。 辅助操作：增加节点（addNode）和移除节点（removeNode） 这两个操作是双向链表的基本操作，用于维护链表的顺序。 addNode(node) ：总是将新节点添加到对应链表的头部。 removeNode(node) ：将指定的节点从它当前所在的双向链表中移除。 总结 LFU 缓存算法通过组合使用哈希表和双向链表，巧妙地维护了键的访问频率和访问时间两个维度的信息。 keyToNode 保证 O(1) 的查询， freqToDList 和 minFreq 共同保证了 O(1) 的淘汰决策。整个设计的关键在于 get 和 put 操作中，对节点在链表间的移动以及对 minFreq 的精确更新。