LFU 缓存

LFU Cache

问题：LFU 缓存

考察：哈希表、链表、设计

来源：DSA Prep / Citadel

链接：https://leetcode.com/problems/lfu-cache

Problem: LFU Cache

Patterns: Hash Table, Linked List, Design

Recency: 6mo

Link: https://leetcode.com/problems/lfu-cache

Source: https://www.dsaprep.dev/blog/citadel-coding-interview-questions/

解析

思路：维护 key 到节点的映射，以及频次到有序链表的映射。get/put 命中时把节点从旧频次链表移到新频次链表；淘汰时从最小频次链表尾部删除最久未使用节点。

复杂度：get/put 平均 O(1)，空间 O(capacity)。