【力扣-146LRU缓存】Python笔记

张开发
• 2026/4/9 15:26:33 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

【力扣-146LRU缓存】Python笔记
面试必杀技：手撕LRU缓存，打通哈希表与双向链表的“任督二脉”摘要：还在为 LRU 缓存算法头秃吗？本文带你彻底吃透“哈希表+双向链表”的黄金组合。通过引入虚拟头尾节点简化边界逻辑，配合清晰的代码注释，助你轻松搞定 LeetCode 146 题，从此面试不慌！📚 核心知识点：为什么是“哈希表 + 双向链表”？在开始写代码之前，咱们得先聊聊为什么。LRU（Least Recently Used，最近最少使用）算法是面试中的“老熟人”了，它的核心需求有两个，而且非常“苛刻”：查找要快：get(key)操作必须是 $O(1)$。顺序调整要快：每次访问或插入数据，都要把它标记为“最近使用”，这也必须是 $O(1)$。这就引出了我们的“黄金搭档”：哈希表（字典）：用来实现O(1)的查找。它负责存储key - 节点的映射，让我们能瞬间定位到数据在哪里。双向链表：用来维护数据的“新鲜度”顺序。为什么是双向？因为当我们想删除一个节点时，必须知道它的“前驱”和“后继”。单向链表做不到O(1）删除。为什么是链表？因为链表在插入和删除节点时，不需要像数组那样移动大量元素，效率极高。通俗理解：把哈希表想象成“地图索引”，把双向链表想象成“排队通道”。新来的或者刚被叫到号的人，直接通过索引找到，然后被安排到队尾（最近使用）。队伍满了，就把队头（最久没用）的人踢出

更多文章