Hot 100 刷题计划】 LeetCode 146. LRU 缓存 | C++ 哈希表+双向链表

LeetCode 146. LRU 缓存

📌 题目描述

题目级别：中等 (实际面试中常作为 Hard 级别压轴)

请你设计并实现一个满足LRU (最近最少使用) 缓存约束的数据结构。
函数get和put必须以O(1)的平均时间复杂度运行。

💡 破题思路：为什么需要哈希表 + 双向链表？

要想在 O(1) 的时间复杂度内完成查找和更新，我们必须使用两种数据结构的组合：

1. 哈希表 (unordered_map)：负责满足get操作的 O(1) 查找。它能瞬间通过key定位到数据在内存中的具体位置。
2. 双向链表 (Doubly Linked List)：负责维持数据的“时间先后顺序”。
   • 为什么不用单链表？因为当我们通过哈希表命中某个节点，想要把它移到头部时，单链表无法在 O(1) 时间内找到它的前驱节点来断开连接，而双向链表有pre指针，可以瞬间“原地拔起”。
   • 为什么不用数组？数组在头部插入或删除元素需要移动大量数据，复杂度是 O(N)。

运作机制：

• 越靠近链表头部的节点，越是“最近使用”的。
• 越靠近链表尾部的节点，越是“最久未使用”的。
• 每次get命中一个节点，就把它从原位置拔出来，重新插到头部 (hinert)。
• 每次put新数据，直接插到头部；如果容量超标，就把尾部节点 (tail->pre) 无情淘汰！

极客细节：虚拟头尾节点
人为在链表两端加上head和tail两个 Dummy 节点，这样任何真实的节点都有前驱和后继，写remove和hinert时再也不用去判断if (node->pre != nullptr)这种恶心的边界条件了。

💻 C++ 代码实现

classNode{public:Node*next;Node*pre;intkey,value;Node(intk,intv){key=k;value=v;next=NULL;pre=NULL;}};classLRUCache{public:LRUCache(intcapacity){cap=capacity;// 初始化虚拟头尾节点，互相指引，彻底消除空指针异常边界head=newNode(0,0);tail=newNode(0,0);head->next=tail;tail->pre=head;}intget(intkey){if(mp.count(key)){// 只要被访问，就说明它是“最近使用”的，立刻把它移到链表头部remove(mp[key]);hinert(mp[key]);returnmp[key]->value;}return-1;}voidput(intkey,intvalue){// 如果 key 已经存在，作者采取了极其果断的策略：// 删掉旧的，重新建个新的插到头部，逻辑异常清晰！if(mp.count(key)){remove(mp[key]);deletemp[key];mp[key]=NULL;}// 创建新节点，执行头插法 (hinert)，并在 map 中记录位置Node*tmp=newNode(key,value);hinert(tmp);mp[key]=tmp;// 如果超出容量限制，启动 LRU 淘汰机制if(mp.size()>cap){// 真实有效节点中，最久没使用的就是 tail 的前一个节点Node*todel=tail->pre;remove(todel);// 从链表中剥离mp.erase(todel->key);// 从哈希表中注销deletetodel;// 释放内存，防止内存泄漏}}// 辅助函数：将节点从双向链表中剥离voidremove(Node*tmp){tmp->pre->next=tmp->next;tmp->next->pre=tmp->pre;}// 辅助函数：头插法 (Head Insert)，将节点插入到虚拟头节点之后voidhinert(Node*tmp){tmp->next=head->next;head->next=tmp;tmp->pre=head;tmp->next->pre=tmp;}private:intcap;Node*head,*tail;unordered_map<int,Node*>mp;// Key 到 链表节点指针 的映射};