濮阳网站建设哪家好,遵义网站建公司,花体字设计,微信小程序永久禁止题目描述 设计和构建一个“最近最少使用”缓存#xff0c;该缓存会删除最近最少使用的项目。缓存应该从键映射到值(允许你插入和检索特定键对应的值)#xff0c;并在初始化时指定最大容量。当缓存被填满时#xff0c;它应该删除最近最少使用的项目。 题目传送门#xff1a;…题目描述 设计和构建一个“最近最少使用”缓存该缓存会删除最近最少使用的项目。缓存应该从键映射到值(允许你插入和检索特定键对应的值)并在初始化时指定最大容量。当缓存被填满时它应该删除最近最少使用的项目。 题目传送门面试题 16.25. LRU 缓存 它应该支持以下操作 获取数据 get 和 写入数据 put 。 获取数据 get(key) - 如果密钥 (key) 存在于缓存中则获取密钥的值总是正数否则返回 -1。 写入数据 put(key, value) - 如果密钥不存在则写入其数据值。当缓存容量达到上限时它应该在写入新数据之前删除最近最少使用的数据值从而为新的数据值留出空间。
示例:
LRUCache cache new LRUCache( 2 /* 缓存容量 */ );cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 该操作会使得密钥 2 作废
cache.get(2); // 返回 -1 (未找到)
cache.put(4, 4); // 该操作会使得密钥 1 作废
cache.get(1); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.get(4); // 返回 4解题思路与代码 这道题我觉得还是有点迷惑性的假如说不了解什么是LRU缓存可能会被“删除最近最少使用”这句话给蒙蔽了双眼而给出了错误的答案。 你可能以为我需要删除的是访问次数相同的最近的那个内存其实不是的。 LRU的原理是如果数据最近被访问过那么将来被访问的几率也更高。因此我们在缓存满的时候会淘汰最长时间未被访问的数据。 所以说做这道题的时候被误导了一下有点难受的。不过知道了原理其实这道题也没有那么的困难。这道题的核心是删除最长时间未被访问过的内存也就是说想办法解决了这个问题这道题也就迎刃而解了。 我们可以考虑用双向链表 unordered_map 去解决这个问题我们每次添加元素都从头开始添加。内存满了删除元素都从队列尾部删除是不是完美的符合了删除最长时间不访问这个元素的需求。 最后我们访问一个链表内的元素我们就把这个元素先从链表中删除把它从新添加到链表头部是不是也完美符合题意 那unordered_map的作用是什么呢它的作用就是让你快速知道你的这查找的这个元素是否在链表内它的查找复杂度是O(1)的。 而双向链表的添加和删除节点的操作本身的时间复杂度也是O(1)的。所以用这两种数据结构可以完美的去均摊这个时间复杂度。
那又因为面试官考你这道题肯定是想要考你自定义双向链表的而不是想看你用库函数。所以我们要自己掌握如何创建并使用一个自定义的双向链表。
其次这就意味着库函数的双向链表不重要了吗恰恰相反它也十分重要真正的工作中肯定也是不可能让你自己创建链表的。所以矛盾又不矛盾。
那接下来就看我给大家展现这两种解法的代码都是如何写的吧~
方案一自定义双向链表 unordered_map
在这道题当中我们需要实现两个函数get 和 put。get函数就是查找缓存中对应key的value。put函数就是把元素放到容器内如果容器满了就挑一个删除了再添加。根据题意当容器满了时我们要删除的元素是最长时间未被使用的元素这里我们使用的容器是双向链表我们每次都从链表的头部开始添加元素如果容器满了需要删除的元素就一定是容器尾部的元素。再者我们如果查询了这个元素而这个元素又在容器内的话我们就要把它重新移动到头部那如何移动呢自然是删除后再添加啦从当前位置删除从链表头部添加。这个自定义双向链表我设置两个哨兵节点分别是head与tail这会使等会的链表操作变得非常的简单。具体的双向链表的其他实现就请大家来看看代码啦~
具体的代码如下
class LRUCache {
public:struct Node{int key;int val;Node * prev;Node * next;Node(int k, int v) : key(k), val(v), prev(nullptr), next(nullptr){};};LRUCache(int capacity) : cap(capacity), size(0), head(new Node(-1,-1)), tail(new Node(-1,-1)) {head-next tail;tail-prev head;}int get(int key) {if(map.find(key) map.end()) return -1;moveNode(map[key]);return map[key]-val;}void put(int key, int value) {if(map.find(key) ! map.end()){map[key]-val value;moveNode(map[key]);}else{if(size cap){map.erase(tail-prev-key);removeFromList(tail-prev);--size;}Node * node new Node(key,value);addToHead(node);map[key] node;size;}}
private:int cap;int size;Node * head;Node * tail;unordered_mapint,Node* map;void addToHead(Node * node){node-next head-next;node-prev head;head-next-prev node;head-next node;}void removeFromList(Node * node){node-next-prev node-prev;node-prev-next node-next;}void moveNode(Node * node){removeFromList(node);addToHead(node);}
};复杂度分析 这个 LRU 缓存的实现无论是 get 还是 put 操作都可以在常数时间内完成因此时间复杂度是 O(1)。 这是因为,我们通过哈希表实现了对任意键值的快速查询查询的时间复杂度是 O(1)。 对于哈希表中存储的每个键值对我们都有一个对应的链表节点。当需要将某个键值对提到最近使用的位置时我们可以直接通过哈希表找到对应的链表节点然后在 O(1) 时间内将其移动到链表的头部。同样当缓存容量已满需要淘汰最久未使用的键值对时我们也可以在 O(1) 时间内从链表尾部删除一个节点。 对于空间复杂度因为哈希表和链表都存储了整个数据所以空间复杂度是 O(capacity)其中 capacity 是缓存的最大容量。
方案二使用list unordered_map
这种做法最大的好处就是带你重新复习了一遍list容器中各种函数的操作。如果你对list函数的操作不太熟悉的话你可以看下我写的这篇文章全面理解C中list双向链表容器的基础概念与函数解析
其他没什么了代码的逻辑和上一种一模一样。
具体的代码如下
class LRUCache {
public:LRUCache(int capacity) : cap(capacity) {}int get(int key) {if(map.find(key) map.end()) return -1;cache.splice(cache.begin(),cache,map[key]);return map[key]-second;}void put(int key, int value) {if(map.find(key) ! map.end()){cache.splice(cache.begin(),cache,map[key]);map[key]-second value;}else{if(cache.size() cap){map.erase(cache.back().first);cache.pop_back(); }cache.push_front({key,value});map[key] cache.begin();}}
private:int cap;listpairint,int cache;unordered_mapint,listpairint,int::iterator map;
};/*** 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)。unordered_map 用哈希实现所以查找的平均时间复杂度是O(1)list::splice方法的时间复杂度也是O(1)。put 方法O(1)。unordered_map的插入和删除操作的平均时间复杂度都是O(1)list::push_front和list::pop_back也都是O(1)。
空间复杂度
O(capacity)。list和unordered_map都存储了缓存中的所有元素所以空间复杂度与缓存的容量成正比。
这就是为什么我们使用 list 和 unordered_map 结构来实现 LRU 缓存的原因它们可以确保所有操作都在常数时间复杂度内完成而且空间复杂度与缓存的容量成正比。
总结 这道题主要是为了测试你对LRULeast Recently Used缓存淘汰策略的理解和实现能力同时也在考察你的数据结构设计能力。 LRU缓存淘汰策略在实际中广泛应用例如在数据库缓存、浏览器缓存等场景中都会有其身影。其核心思想是“如果一个数据在最近一段时间没有被访问到那么在将来它被访问的可能性也很小”。因此这种算法可以用于预测哪些数据应该被替换出去从而使缓存的命中率最大。 实现这个策略需要用到的数据结构包括哈希表HashMap和双向链表Doubly LinkedList。其中哈希表提供了快速查找而双向链表则可以用来调整数据的优先级。
通过这道题你可以锻炼并展示出你对以上各种技术和数据结构的掌握程度。同时这也是一种非常实用的技能可以直接应用于你未来的项目和工作中。
最后的最后如果你觉得我的这篇文章写的不错的话请给我一个赞与收藏关注我我会继续给大家带来更多更优质的干货内容。 文章转载自： http://www.morning.jwxnr.cn.gov.cn.jwxnr.cn http://www.morning.jgttx.cn.gov.cn.jgttx.cn http://www.morning.mzqhb.cn.gov.cn.mzqhb.cn http://www.morning.cnfjs.cn.gov.cn.cnfjs.cn http://www.morning.fpxms.cn.gov.cn.fpxms.cn http://www.morning.xpgwz.cn.gov.cn.xpgwz.cn http://www.morning.wxlzr.cn.gov.cn.wxlzr.cn http://www.morning.kfmnf.cn.gov.cn.kfmnf.cn http://www.morning.dhyqg.cn.gov.cn.dhyqg.cn http://www.morning.cykqg.cn.gov.cn.cykqg.cn http://www.morning.gjzwj.cn.gov.cn.gjzwj.cn http://www.morning.rlbc.cn.gov.cn.rlbc.cn http://www.morning.jwcmq.cn.gov.cn.jwcmq.cn http://www.morning.pxsn.cn.gov.cn.pxsn.cn http://www.morning.pqwjh.cn.gov.cn.pqwjh.cn http://www.morning.yaqi6.com.gov.cn.yaqi6.com http://www.morning.ylpwc.cn.gov.cn.ylpwc.cn http://www.morning.tpchy.cn.gov.cn.tpchy.cn http://www.morning.fglzk.cn.gov.cn.fglzk.cn http://www.morning.mqfw.cn.gov.cn.mqfw.cn http://www.morning.qwwhs.cn.gov.cn.qwwhs.cn http://www.morning.jcyrs.cn.gov.cn.jcyrs.cn http://www.morning.nmrtb.cn.gov.cn.nmrtb.cn http://www.morning.pjbhk.cn.gov.cn.pjbhk.cn http://www.morning.mtgkq.cn.gov.cn.mtgkq.cn http://www.morning.xnbd.cn.gov.cn.xnbd.cn http://www.morning.rqrh.cn.gov.cn.rqrh.cn http://www.morning.cnbdn.cn.gov.cn.cnbdn.cn http://www.morning.qrqg.cn.gov.cn.qrqg.cn http://www.morning.bykqg.cn.gov.cn.bykqg.cn http://www.morning.qjbxt.cn.gov.cn.qjbxt.cn http://www.morning.smdnl.cn.gov.cn.smdnl.cn http://www.morning.fengnue.com.gov.cn.fengnue.com http://www.morning.pqrhb.cn.gov.cn.pqrhb.cn http://www.morning.pfntr.cn.gov.cn.pfntr.cn http://www.morning.lstmq.cn.gov.cn.lstmq.cn http://www.morning.chehb.com.gov.cn.chehb.com http://www.morning.yzfrh.cn.gov.cn.yzfrh.cn http://www.morning.nptls.cn.gov.cn.nptls.cn http://www.morning.rtlg.cn.gov.cn.rtlg.cn http://www.morning.ryywf.cn.gov.cn.ryywf.cn http://www.morning.hybmz.cn.gov.cn.hybmz.cn http://www.morning.fplwz.cn.gov.cn.fplwz.cn http://www.morning.yrflh.cn.gov.cn.yrflh.cn http://www.morning.ylph.cn.gov.cn.ylph.cn http://www.morning.skwwj.cn.gov.cn.skwwj.cn http://www.morning.rrwgh.cn.gov.cn.rrwgh.cn http://www.morning.ygth.cn.gov.cn.ygth.cn http://www.morning.zmlnp.cn.gov.cn.zmlnp.cn http://www.morning.hjlwt.cn.gov.cn.hjlwt.cn http://www.morning.ppghc.cn.gov.cn.ppghc.cn http://www.morning.tkflb.cn.gov.cn.tkflb.cn http://www.morning.pjbhk.cn.gov.cn.pjbhk.cn http://www.morning.mmqhq.cn.gov.cn.mmqhq.cn http://www.morning.wklrz.cn.gov.cn.wklrz.cn http://www.morning.jcbmm.cn.gov.cn.jcbmm.cn http://www.morning.sbdqy.cn.gov.cn.sbdqy.cn http://www.morning.kbdrq.cn.gov.cn.kbdrq.cn http://www.morning.zxxys.cn.gov.cn.zxxys.cn http://www.morning.plxnn.cn.gov.cn.plxnn.cn http://www.morning.ptxwg.cn.gov.cn.ptxwg.cn http://www.morning.hsgxj.cn.gov.cn.hsgxj.cn http://www.morning.kwqcy.cn.gov.cn.kwqcy.cn http://www.morning.skrxp.cn.gov.cn.skrxp.cn http://www.morning.wqrk.cn.gov.cn.wqrk.cn http://www.morning.qjrjs.cn.gov.cn.qjrjs.cn http://www.morning.wgqtt.cn.gov.cn.wgqtt.cn http://www.morning.qkrqt.cn.gov.cn.qkrqt.cn http://www.morning.jlschmy.com.gov.cn.jlschmy.com http://www.morning.qpnmd.cn.gov.cn.qpnmd.cn http://www.morning.rttkl.cn.gov.cn.rttkl.cn http://www.morning.lzjxn.cn.gov.cn.lzjxn.cn http://www.morning.tpyjr.cn.gov.cn.tpyjr.cn http://www.morning.kdtdh.cn.gov.cn.kdtdh.cn http://www.morning.hksxq.cn.gov.cn.hksxq.cn http://www.morning.mmjyk.cn.gov.cn.mmjyk.cn http://www.morning.cljpz.cn.gov.cn.cljpz.cn http://www.morning.tkchm.cn.gov.cn.tkchm.cn http://www.morning.xxhc.cn.gov.cn.xxhc.cn http://www.morning.xhklb.cn.gov.cn.xhklb.cn
