【链表】LC 146.LRU缓存
文章目录
- 前言
- 一、题目
- 1、原题链接
- 2、题目描述
- 二、个人思路整理
- 1、思路分析
- 数据结构设计
- 核心操作
- 2、解题代码
- 三、知识风暴
前言
本专栏文章为《LeetCode 热题 100》的刷题题解，相关内容如有侵权，立即删除。
一、题目
1、原题链接
146.LRU缓存
2、题目描述
二、个人思路整理
1、思路分析
参考【图解】一张图秒懂 LRU！（Python/Java/C++/Go/JS/Rust），辅助理解。
数据结构设计
双向链表：维护数据的访问时效性。
- 靠近
head的节点代表最近访问（Most Recently Used）。 - 靠近
tail的节点代表最久未使用（Least Recently Used）。 - 节点中必须同时保存
key和val。保留key的原因是：当缓存满淘汰尾部节点时，需要根据节点的key将其从哈希表中同步删除。 - 引入伪头部
head和伪尾部tail哨兵节点，避免插入和删除时判断指针为空的边界情况。
- 靠近
哈希表（
unordered_map<int, Node*> cache）：建立key -> 链表节点指针的映射，使得查找节点只需O ( 1 ) O(1)O(1)。
核心操作
get(key)- 在哈希表
cache中查找key。 - 若不存在，直接返回
-1。 - 若存在，通过哈希表拿到对应节点指针，将该节点移动到双向链表头部（表示刚被访问），返回
node->val。
- 在哈希表
put(key, value)- 在哈希表
cache中查找key。 - 若
key已存在：- 更新该节点的
val。 - 将该节点移动到双向链表头部。
- 更新该节点的
- 若
key不存在：- 检查当前节点数量是否达到
capacity。 - 若已满，删除
tail前一个节点（即最久未使用的真实尾节点），并在哈希表中删除其对应的key。 - 创建新节点
(key, value)，插入到head之后，并在哈希表中记录cache[key] = new_node。
- 检查当前节点数量是否达到
- 在哈希表
2、解题代码
classLRUCache{private:// 双向链表节点定义structNode{intkey;// 存储 key，用于淘汰尾部节点时在哈希表中反查并删除intval;// 存储 valueNode*prev;// 前驱指针Node*next;// 后继指针Node(intk=0,intv=0):key(k),val(v),prev(nullptr),next(nullptr){}};intcap;// 缓存最大容量intsize;// 当前缓存中的节点数量Node*head;// 伪头部节点（靠近 head 的是最近访问的节点）Node*tail;// 伪尾部节点（靠近 tail 的是最久未访问的节点）unordered_map<int,Node*>cache;// 哈希表：映射 key->双向链表节点指针，实现 O(1)查找// 从双向链表中移除给定节点 nodevoidremoveNode(Node*node){node->prev->next=node->next;node->next->prev=node->prev;}// 将节点 node 插入到伪头部 head 之后（标记为最近使用）voidaddToHead(Node*node){node->next=head->next;node->prev=head;head->next->prev=node;head->next=node;}// 将已在链表中的节点移动到头部（先摘除，再插入头部）voidmoveToHead(Node*node){removeNode(node);addToHead(node);}// 淘汰并返回链表中实际最久未使用的节点（即 tail 前面的节点）Node*removeTail(){Node*node=tail->prev;removeNode(node);returnnode;}public:// 初始化 LRU 缓存，建立伪头部和伪尾部的双向连接LRUCache(intcapacity):cap(capacity),size(0){head=newNode();tail=newNode();head->next=tail;tail->prev=head;}// 析构函数：释放链表所有动态分配的节点内存，防止内存泄漏~LRUCache(){Node*curr=head;while(curr!=nullptr){Node*nextNode=curr->next;deletecurr;curr=nextNode;}}// 获取数据：存在则刷新访问顺序并返回值不存在返回 -1intget(intkey){autoit=cache.find(key);if(it==cache.end()){return-1;// 未命中}// 命中：获取节点并将其移动到链表头部（刷新时效性）Node*node=it->second;moveToHead(node);returnnode->val;}// 插入或更新数据voidput(intkey,intvalue){autoit=cache.find(key);if(it!=cache.end()){// 1. key已存在：更新 value 并移到链表头部Node*node=it->second;node->val=value;moveToHead(node);}else{// 2. key不存在：创建新节点并加入链表头部与哈希表Node*newNode=newNode(key,value);cache[key]=newNode;addToHead(newNode);size++;// 若超出容量限制，淘汰最久未使用的尾部节点if(size>cap){Node*removed=removeTail();cache.erase(removed->key);// 同步从哈希表中移除deleteremoved;// 释放物理内存size--;}}}};/** * Your LRUCache object will be instantiated and called as such: * LRUCache* obj = new LRUCache(capacity); * int param_1 = obj->get(key); * obj->put(key,value); */复杂度分析
- 时间复杂度：
get：O ( 1 ) O(1)O(1)，哈希表查找和链表节点移动均为常数时间。put：O ( 1 ) O(1)O(1)，哈希表插入/删除与链表节点插入/删除均为常数时间。- 空间复杂度：O ( capacity ) O(\text{capacity})O(capacity)，哈希表和双向链表最多存储capacity + 1 \text{capacity} + 1capacity+1个元素（处理新节点时是先加后删）。
三、知识风暴
哈希表 + 双向链表是本题的核心思想：利用哈希表实现O ( 1 ) O(1)O(1)的查找，配合双向链表维护数据的访问时效性，在O ( 1 ) O(1)O(1)时间内完成get和put操作。
算法核心思想：
- 哈希表定位：
cache建立key -> 链表节点指针的映射，使查找任意节点只需O ( 1 ) O(1)O(1)，无需遍历链表。 - 双向链表维护时效：靠近
head的节点代表最近访问，靠近tail的节点代表最久未使用，插入和删除均为O ( 1 ) O(1)O(1)。 - 哨兵节点简化边界：伪头部
head和伪尾部tail避免插入和删除时判断指针为空的边界情况。 - 淘汰策略：缓存满时删除
tail前一个节点（最久未使用），并同步从哈希表中删除对应key，保证数据一致性。
使用要点：
- 先查后改：
put时先查哈希表，若key已存在则更新val并移到头部，不存在则新建节点插入头部。 - 先加后删：插入新节点时先
size++，若超出capacity再淘汰尾部节点并size--，避免容量判断出错。 - 同步删除：淘汰尾部节点时，必须用其
key从哈希表中同步删除，否则哈希表残留脏数据。 - 内存释放：淘汰节点后
delete removed释放物理内存，防止内存泄漏。 - 析构清理：析构函数遍历链表释放所有节点，避免程序退出时内存泄漏。
- 类型定义加分号：C++ 中
struct、class、enum定义的大括号后必须加分号（;），否则编译报错。设计原因是 C++ 语法允许在定义类型的同时顺便声明变量（如struct Point { int x; } p1;），分号是整条声明语句的结束标记。容易混淆的是：函数体、if/for语句块、namespace以及其他现代语言（如 Java/Go/Rust）的大括号后均不需要加分号。
算法变体与扩展：
- LFU 缓存：按访问频率淘汰，频率相同再按时间淘汰，需额外维护频率计数器（对应 LeetCode 460）。
- 哈希表 + 单链表：若只维护访问顺序不要求O ( 1 ) O(1)O(1)删除，可用单链表简化实现，但删除需O ( n ) O(n)O(n)遍历。
- 哈希表 + 数组：用数组模拟双向链表（下标代替指针），避免动态内存分配，适合嵌入式等受限环境。
- 并发 LRU：多线程环境下需加锁保护哈希表和链表，或用读写锁优化读多写少场景。
相关 LeetCode 例题：
- 460. LFU 缓存（按访问频率淘汰，需维护频率计数器）
- 146. LRU 缓存（本题，哈希表 + 双向链表）
- 剑指 Offer II 031. 最近最少使用缓存（LRU 缓存变体）
- 面试题 16.25. LRU 缓存（LRU 缓存面试题）