LRU 变种:访问达到 k 次才进入缓存(LRU-K)
哪些公司问过
答案要点
- 访问次数未达 k 的 key 只记录在历史表,不占缓存空间
- 历史表也需设容量上限,可用 LRU 或 FIFO 淘汰旧记录
- 正式缓存用哈希表加双向链表,与 LC146 相同
- 计数达到 k 时从历史表迁入缓存头部,缓存满则淘汰尾部
- 各操作 O(1);k=1 时退化为普通 LRU
易错点
- 历史表不设上限,长期运行后内存无限增长
- 未在缓存中的 get 没有计数,导致永远无法达到 k 次
- 迁入缓存时忘记从历史表删除,计数和状态不一致
面试官常见追问
- LRU-K 解决了普通 LRU 的什么问题?
- k 取多大合适?
- 如果规则是未达 k 次的节点不参与淘汰呢?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。