ToB企服应用市场:ToB评测及商务社交产业平台

标题: LeetCode 热题 100_LRU 缓存（35_146_中等_C++）(哈希表 + 双向链表)(构造 [打印本页]

---

作者: 王海鱼    时间: 2024-12-30 10:11
标题: LeetCode 热题 100_LRU 缓存（35_146_中等_C++）(哈希表 + 双向链表)(构造
题目形貌：

请你设计并实现一个满足 LRU (近来最少使用) 缓存 约束的数据布局。
实现 LRUCache 类：
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变动其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数目超过 capacity ，则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
输入输出样例：

示例 ：
输入
[“LRUCache”, “put”, “put”, “get”, “put”, “get”, “put”, “get”, “get”, “get”]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]
表明
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4
提示：
1 <= capacity <= 3000
0 <= key <= 10000
0 <= value <= 105
最多调用 2 * 105 次 get 和 put
题解：

解题思路：

思路一（哈希表 + 双向链表）：
1、通过题目分析，put操作：如果key不在缓存中那我们需要进行结点的插入操作，若插入时缓存已满则先删除最久未访问的结点再插入。这里我们可以想到双向链表，头部存储近来访问结点，尾部存储最久未访问结点。get操作，若存在key则返回结点的value，这里get相称于一个查找，所以我们可以想到哈希表，如许我们就能快速的进行结点的查找和定位。
2、具体思路如下：
① 我们创建一个头结点和一个额外的尾结点来方便结点的插入和删除操作。
② 插入操作（put）：我们将刚插入的元素或者近来使用的元素放在链表的头部，则尾部为最长时间未使用的元素。
     若要插入结点key时，之前存在序号为key的结点则移到链表头部。
     若要插入节点key时，之前不存在序号为key的结点，且结点数未满则插入链表头部，若结点数已满则插入后删除尾结点。
③ 获取操作（get）：分析到获取我们很快能想到哈希表，因哈希表能让我们快速的进行查找操作，所以上述插入和删除时需要维护一个哈希表。
     若结点不在哈希表中则返回-1。
     若存在哈希表中则返回值，并将结点移动到头部。
力扣官方题解链接（有缓存 get() 和put () 过程图很不错）
3、复杂度分析
① 时间复杂度：对于 put 和 get 都是 O(1)。
② 空间复杂度：O(capacity)，因为哈希表和双向链表最多存储 capacity+1 个元素。
代码实现（思路一（哈希表 + 双向链表））：

1. struct DLinkedNode{
2.         int key,value;
3.         DLinkedNode* prev;
4.         DLinkedNode* next;
5.         DLinkedNode():key(0),value(0),prev(nullptr),next(nullptr){}
6.         DLinkedNode(int _key,int _value):key(_key),value(_value),prev(nullptr),next(nullptr){}
7. };
9. class LRUCache {
11. private:
12.         //存储缓存中的节点数
13.         unordered_map<int,DLinkedNode*> cache;
14.         //head和tail方便结点的操作
15.         DLinkedNode* head;
16.         DLinkedNode* tail;
17.         //size是当前缓存中的结点数，capacity是缓存最大的容量
18.         int size;
19.         int capacity;
20.        
21. public:
22.         //初始化缓存，缓存容量为 _capacity，一开始缓存存入size=0个结点
23.     LRUCache(int _capacity):capacity(_capacity),size(0){
24.             head=new DLinkedNode();
25.             tail=new DLinkedNode();
26.             head->next=tail;
27.             tail->prev=head;
28.         }
29.         //如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1
30.         int get(int key){
31.                 if(!cache.count(key)){
32.                         return -1;
33.                 }
34.                 //若存在key，则将key对应的结点移动到链表首部，先拆出来，再添加到首部
35.                 removeNode(cache[key]);
36.                 addToHead(cache[key]);
37.                 return cache[key]->value;
38.         }
39.        
40.         void put(int key,int value){
41.                 //如果关键字 key 已经存在，则变更其数据值 value
42.                 if(cache.count(key)){
43.                         removeNode(cache[key]);
44.                         addToHead(cache[key]);
45.                         cache[key]->value=value;
46.                 //如果不存在，则向缓存中插入该组 key-value
47.                 }else{
48.                         DLinkedNode *newNode=new DLinkedNode(key,value);
49.                         cache[key]=newNode;
50.                         addToHead(newNode);
51.                         ++size;
52.                         //如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
53.                         if(size>capacity){
54.                                 DLinkedNode *removed=removeTail();
55.                                 cache.erase(removed->key);
56.                                 delete removed;
57.                                 --size;
58.                         }
59.                 }
60.         }
61.        
62.         //插入链表头部
63.         void addToHead(DLinkedNode *node){
64.                 node->next=head->next;
65.                 node->prev=head;
66.                 head->next->prev=node;
67.                 head->next=node;
68.         }
69.        
70.         //断开链表尾部（需返回，用于删除哈希表中对应数据）
71.         DLinkedNode *removeTail(){
72.                 DLinkedNode *node=tail->prev;
73.                
74.                 tail->prev=node->prev;
75.                 node->prev->next=tail;
76.                 return node;
77.         }
78.        
79.         //断开结点
80.         void removeNode(DLinkedNode* node) {
81.         node->prev->next = node->next;
82.         node->next->prev = node->prev;
83.     }
84. };

复制代码

部分代码解读

构造函数声明+初始化列表进行变量初始化和赋值

1. //下方代码的用法和第一行相同，是构造函数初始化列表，对变量初始化和赋值
2. DLinkedNode(int _key,int _value):key(_key),value(_value),prev(nullptr),next(nullptr){}
3. //构造函数
4. //初始化 capacity 成员变量 为传递给构造函数的参数 _capacity
5. //初始化 size 成员变量 为 0，表示缓存初始化时为空。
6. LRUCache(int _capacity):capacity(_capacity),size(0){}

复制代码

LeetCode 热题 100_LRU 缓存（35_146)原题链接
欢迎各人和我沟通交流(✿◠‿◠)

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

---

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)

Powered by Discuz! X3.4