合肥建设工程交易网站,wordpress 默认图片路径,深圳外贸电商网站建设,信息可视化网站力扣题目链接 题意#xff1a;本题的题意就是希望我们设计一个满足 LRU 缓存的数据结构#xff0c;LRU即最近最少使用。 需要我们实现 get 和 put 方法#xff0c;即从缓存中获取值和设置缓存中值的方法。 还有一个约束条件就是缓存应当有容量限制#xff0c;如果实现 put … 力扣题目链接 题意本题的题意就是希望我们设计一个满足 LRU 缓存的数据结构LRU即最近最少使用。 需要我们实现 get 和 put 方法即从缓存中获取值和设置缓存中值的方法。 还有一个约束条件就是缓存应当有容量限制如果实现 put 方法的时候没有空闲的空间的话需要淘汰一个最久没有使用的 key 同时要求 get 和 put 的时间复杂度是 O(1) 其实关于 LRU 最类似的一种应用就是浏览器记录随着我们打开的浏览器越来越多浏览历史表就会越来越长如果我们想要打开某个浏览页面也会直接从缓存中读取并且由于我们打开了历史记录中的某个浏览页面它会成为最新的那条记录。 文章目录 测试用例解读总体代码简洁实现类成员变量构造函数get 方法put 方法 测试用例解读
可以直接看 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_mapint, 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::liststd::pairint, int cacheList; // Stores the (key, value) pairsstd::unordered_mapint, std::liststd::pairint, int::iterator cacheMap; // Maps key to the corresponding iterator in cacheList
};类成员变量
首先定义一个类成员变量
class LRUCache {
private:int capacity_;std::liststd::pairint, int cacheList_; // Stores the (key, value) pairsstd::unordered_mapint, std::liststd::pairint, int::iterator cacheMap_; // Maps key to the corresponding iterator in cacheList
};这里的 cacheList 即我们之前所维护的那个双向链表 cacheMap 就是我们之前维护的那个 hashMap key 是键值 value 是我们之前的链表节点。
在此之前我们自己定义个用于缓存的节点但是我们可以直接使用 std::pairint, int 来代替我们自己构造的类
除此之外std::pairint, int::iterator 是一个类型声明用于表示指向 std::liststd::pairint, 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();}}
