前言

本专栏文章为《LeetCode 热题 100》的刷题题解，相关内容如有侵权，立即删除。

一、题目

1、原题链接

146.LRU缓存

2、题目描述

二、个人思路整理

1、思路分析

参考【图解】一张图秒懂 LRU！（Python/Java/C++/Go/JS/Rust），辅助理解。

数据结构设计

1. 双向链表：维护数据的访问时效性。

   • 靠近head的节点代表最近访问（Most Recently Used）。
   • 靠近tail的节点代表最久未使用（Least Recently Used）。
   • 节点中必须同时保存key和val。保留key的原因是：当缓存满淘汰尾部节点时，需要根据节点的key将其从哈希表中同步删除。
   • 引入伪头部head和伪尾部tail哨兵节点，避免插入和删除时判断指针为空的边界情况。

2. 哈希表（unordered_map<int, Node*> cache）：建立key -> 链表节点指针的映射，使得查找节点只需O ( 1 ) O(1)O(1)。

核心操作

1. get(key)

   1. 在哈希表cache中查找key。
   2. 若不存在，直接返回-1。
   3. 若存在，通过哈希表拿到对应节点指针，将该节点移动到双向链表头部（表示刚被访问），返回node->val。

2. put(key, value)

   1. 在哈希表cache中查找key。
   2. 若key已存在：
      • 更新该节点的val。
      • 将该节点移动到双向链表头部。
   3. 若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 缓存面试题）