LeetCode Medium｜【146. LRU 缓存】

力扣题目链接

题意：本题的题意就是希望我们设计一个满足 LRU 缓存的数据结构，LRU即最近最少使用。
需要我们实现 get 和 put 方法，即从缓存中获取值和设置缓存中值的方法。
还有一个约束条件就是缓存应当有容量限制，如果实现 put 方法的时候，没有空闲的空间的话，需要淘汰一个最久没有使用的 key
同时要求 get 和 put 的时间复杂度是 O(1)

其实关于 LRU 最类似的一种应用就是浏览器记录，随着我们打开的浏览器越来越多，浏览历史表就会越来越长，如果我们想要打开某个浏览页面，也会直接从缓存中读取，并且由于我们打开了历史记录中的某个浏览页面，它会成为最新的那条记录。

测试用例解读

可以直接看 B 站视频 ：【大厂面试官让我手写LRU缓存，还好提前抱了佛脚，春招有希望了】(具体位置从 3:00开始)

首先我们一个一个解决上面提出的几个问题：

• 首先关于我们要求的 get 查询方法，很直观的一个想法就是使用 map 来进行实现，不过他只能实现查询时间复杂度为 O(1)，但是由于 map 本身是无序的，所以我们希望他能够有新旧顺序的信息。
• 很直观的思路，我们每次新建一个键值对的时候，就把这个 key-value 放入一个链表的头，我们每次存入新的节点，我们就把其作为新的头。这样我们链表的头部永远都是那个最新的 key-value；链表的尾部就是最久未使用的键值对
• 但是我们仍然有一个很重要的问题无法实现：如果我们查询了某个 key-value ，并且该节点在链表的中间位置，那么我们就不能及时得将该节点放到链表的头部。因为我们的 map 是以 key-value 来进行存取的，所以我们不能在链表中及时找到对应的节点
• 为了应对上面的情况，有一个比较好的思路就是，当我们存储节点时，map 中的 key 就是该节点的键，map 中的 value 就是该节点所在链表的节点（ListNode*）。通过这样的方法，我们可以快速定位到链表节点，而不需要根据别的信息进行遍历。
• 根据以上的要求，我们可以知道，使用单向链表是无法实现上述想法的，因为我们的节点是需要往前移动到链表头部，所以这里的数据结构使用双向链表。

总上所述，我们的代码雏形就出来了。

总体代码

• 首先定义双向链表的节点结构：每个结构包括 key-value 的值和 prev 和 next 指针，并且定义两个构造函数

struct Node {int key, value;Node *prev, *next;Node() : key(0), value(0), prev(nullptr), next(nullptr) {}Node(int key, int value) : key(key), value(value), prev(nullptr), next(nullptr) {}
};

• 下面来实现 LRU 缓存：定义链表的虚拟头、尾节点；哈希表来存储 key 和 双向链表节点 的映射关系；最后是我们的容量大小，以及当前已使用的大小。

class LRUCache {
private:std::unordered_map<int, Node*> hashMap_;int capacity_, size_;Node *dummyHead_, *dummyTail_;
};

• 实现 LRUCache 的构造函数：

class LRUCache {
private:...
public: LRUCache(int capacity) : capacity_(capacity), size_(0) {dummyHead_ = new Node();dummyTail_ = new Node();dummyHead_->next = dummyTail_;dummyTail_->prev = dummyHead_;}

• 接下来我们来实现从链表中删除节点和插入节点到链表头的方法，该方法是其中的 get 和 put 方法中的重要：

    void removeNode(Node* node) {node->prev->next = node->next;node->next->prev = node->prev;}// 在头节点处插入一个 nodevoid addNodeToHead(Node* node) {node->prev = dummyHead_;node->next = dummyHead_->next;dummyHead_->next->prev = node;dummyHead_->next = node;}

• 接下来实现重要的 get 方法：首先我们需要确定节点时候在哈希表中：

    int get(int key) {if (hashMap_.find(key) != hashMap_.end()) {Node* node = hashMap_[key];removeNode(node);addNodeToHead(node);return node->value;}return -1;}

• 随后是设置节点的值：如果该节点在哈希表中存在的话，我们就重新设置其节点的值，随后更新其位置在最前面；如果不存在的话，说明要插入一个新的节点，我们首先要判断一下容量，如果容量达到了上限，我们就需要从链表的尾部淘汰一个节点，然后在进行插入

    void put(int key, int value) {if (hashMap_.find(key) != hashMap_.end()) {Node* node = hashMap_[key];node->value = value;removeNode(node);addNodeToHead(node);} else {if (size_ == capacity_) {Node* removed = dummyTail_->prev;hashMap_.erase(removed->key);removeNode(removed);delete removed;size_--;}Node* node = new Node(key, value);addNodeToHead(node);hashMap_[key] = node;size_++;}}

简洁实现

这里介绍一个简介实现，如下：

class LRUCache {
public:LRUCache(int capacity) : capacity_(capacity) {}int get(int key) {auto it = cacheMap.find(key);if (it == cacheMap.end()) {return -1; // Key not found} else {// Move the accessed (key, value) pair to the front of the cacheListcacheList.splice(cacheList.begin(), cacheList, it->second);return it->second->second;}}void put(int key, int value) {auto it = cacheMap.find(key);if (it != cacheMap.end()) {// Key already exists, update the value and move it to the frontit->second->second = value;cacheList.splice(cacheList.begin(), cacheList, it->second);} else {if (cacheList.size() == capacity_) {// Cache is full, remove the least recently used itemauto last = cacheList.back();cacheMap.erase(last.first);cacheList.pop_back();}// Insert the new key-value pair at the frontcacheList.emplace_front(key, value);cacheMap[key] = cacheList.begin();}}private:int capacity_;std::list<std::pair<int, int>> cacheList; // Stores the (key, value) pairsstd::unordered_map<int, std::list<std::pair<int, int>>::iterator> cacheMap; // Maps key to the corresponding iterator in cacheList
};

类成员变量

首先定义一个类成员变量：

class LRUCache {
private:int capacity_;std::list<std::pair<int, int>> cacheList_; // Stores the (key, value) pairsstd::unordered_map<int, std::list<std::pair<int, int>>::iterator> cacheMap_; // Maps key to the corresponding iterator in cacheList
};

这里的 cacheList 即我们之前所维护的那个双向链表；
cacheMap 就是我们之前维护的那个 hashMap ，key 是键值， value 是我们之前的链表节点。

在此之前，我们自己定义个用于缓存的节点，但是我们可以直接使用 std::pair<int, int> 来代替我们自己构造的类；

除此之外：std::pair<int, int>>::iterator 是一个类型声明，用于表示指向 std::list<std::pair<int, int>> 中元素的迭代器，这个迭代器类型可以用来遍历或访问 std::list 容器中的元素。

接下来我们开始进行主要成员方法的实现：

构造函数

class LRUCache {
public:LRUCache(int capacity) : capacity_(capacity) {}
private:...
};

get 方法

    int get(int key) {auto it = cacheMap_.find(key);if (it == cacheMap_.end()) {return -1; // Key not found} else {// Move the accessed (key, value) pair to the front of the cacheListcacheList_.splice(cacheList_.begin(), cacheList_, it->second);return it->second->second;}}

put 方法

    void put(int key, int value) {auto it = cacheMap_.find(key);if (it != cacheMap_.end()) {// Key already exists, update the value and move it to the frontit->second->second = value;cacheList_.splice(cacheList_.begin(), cacheList_, it->second);} else {if (cacheList_.size() == capacity_) {// Cache is full, remove the least recently used itemauto last = cacheList_.back();cacheMap_.erase(last.first);cacheList_.pop_back();}// Insert the new key-value pair at the frontcacheList_.emplace_front(key, value);cacheMap_[key] = cacheList_.begin();}}