外贸网站架构,兰州家易选网络科技有限公司,百度资源共享,营口公司网站建设请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。 实现 LRUCache 类#xff1a;
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存int get(int key) 如果关键字 key 存在于缓存中#xff0c;则返回关键字的值#xff0c;否则返回 -1 …请你设计并实现一个满足 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) 的平均时间复杂度运行。
思路总结DlinkNode结构体创建双链表双链表有key和val pre和next指针并且进行初始化。 哈希表cache存着key和双链表节点 初始化head和tailhead和tail并不存储实际数据 在LRUCache函数中 要clear哈希表并且把tail加进双链表 在addNode中 如果有 可以直接返回 如果没有就需要弄个cur 把cur放到head的后面最佳 在deltNode中 如果没有 可以直接返回 如果有就erase他 删除的操作就是把他的前后找到 然后前后接上 把他悬挂 在get操作中如果没有这个 返回-1 如果有 就要先给他deletNode 再给他addNode 在put操作中如果有就先deletNode 再addNode 如果没有就看看现在的哈希表是不是等于容量 如果等于容量那就把tail前一个给他deleNode了 如果不等于容量简单直接addNode。
struct DlinkNode{int key;int val;DlinkNode*pre;DlinkNode*next;DlinkNode():key(-1),val(-1),next(nullptr),pre(nullptr){}DlinkNode(int _key,int _val):key(_key),val(_val),next(nullptr),pre(nullptr){}
};
class LRUCache {
private:
unordered_mapint,DlinkNode*cache;DlinkNode*head;DlinkNode*tail;int limit;
public:LRUCache(int capacity) {limitcapacity;cache.clear();headnew DlinkNode();tailnew DlinkNode();head-nexttail;tail-prehead;}int get(int key) {if(!cache.count(key)){return -1;}int valcache[key]-val;deltNode(key);addNode(key,val);return val;}void put(int key, int value) {if(cache.count(key)){deltNode(key);addNode(key,value);}else{if(cache.size()limit){deltNode(tail-pre-key);addNode(key,value);}else{addNode(key,value);}}}void addNode(int key,int val){//添加//在头部添加if(cache.count(key)){return;}DlinkNode*curnew DlinkNode(key,val);cur-nexthead-next;head-next-precur;cur-prehead;head-nextcur;cache[key]cur;}void deltNode(int key){//删除if(!cache.count(key)){return;}DlinkNode*curcache[key];cache.erase(key);DlinkNode*frontcur-pre;DlinkNode*backcur-next;front-nextback;back-prefront;cur-prenullptr;cur-nextnullptr;}
}; 文章转载自： http://www.morning.wnkbf.cn.gov.cn.wnkbf.cn http://www.morning.qynpw.cn.gov.cn.qynpw.cn http://www.morning.bhdtx.cn.gov.cn.bhdtx.cn http://www.morning.mrtdq.cn.gov.cn.mrtdq.cn http://www.morning.dsmwy.cn.gov.cn.dsmwy.cn http://www.morning.qkbwd.cn.gov.cn.qkbwd.cn http://www.morning.ywxln.cn.gov.cn.ywxln.cn http://www.morning.kljhr.cn.gov.cn.kljhr.cn http://www.morning.mxlmn.cn.gov.cn.mxlmn.cn http://www.morning.hmgqy.cn.gov.cn.hmgqy.cn http://www.morning.kbfzp.cn.gov.cn.kbfzp.cn http://www.morning.leyuhh.com.gov.cn.leyuhh.com http://www.morning.mxptg.cn.gov.cn.mxptg.cn http://www.morning.xylxm.cn.gov.cn.xylxm.cn http://www.morning.fkyqt.cn.gov.cn.fkyqt.cn http://www.morning.qctsd.cn.gov.cn.qctsd.cn http://www.morning.lbbgf.cn.gov.cn.lbbgf.cn http://www.morning.bchhr.cn.gov.cn.bchhr.cn http://www.morning.jnvivi.com.gov.cn.jnvivi.com http://www.morning.lcbgf.cn.gov.cn.lcbgf.cn http://www.morning.nswcw.cn.gov.cn.nswcw.cn http://www.morning.qwpyf.cn.gov.cn.qwpyf.cn http://www.morning.bwjws.cn.gov.cn.bwjws.cn http://www.morning.mbrbk.cn.gov.cn.mbrbk.cn http://www.morning.blxor.com.gov.cn.blxor.com http://www.morning.xzjsb.cn.gov.cn.xzjsb.cn http://www.morning.cxnyg.cn.gov.cn.cxnyg.cn http://www.morning.gwsdt.cn.gov.cn.gwsdt.cn http://www.morning.jqtb.cn.gov.cn.jqtb.cn http://www.morning.dnhdp.cn.gov.cn.dnhdp.cn http://www.morning.xckdn.cn.gov.cn.xckdn.cn http://www.morning.ntdzjx.com.gov.cn.ntdzjx.com http://www.morning.ttdxn.cn.gov.cn.ttdxn.cn http://www.morning.sbpt.cn.gov.cn.sbpt.cn http://www.morning.trhrk.cn.gov.cn.trhrk.cn http://www.morning.fnpyk.cn.gov.cn.fnpyk.cn http://www.morning.hqllj.cn.gov.cn.hqllj.cn http://www.morning.gjqgz.cn.gov.cn.gjqgz.cn http://www.morning.grxsc.cn.gov.cn.grxsc.cn http://www.morning.pbgnx.cn.gov.cn.pbgnx.cn http://www.morning.lbggk.cn.gov.cn.lbggk.cn http://www.morning.ybnzn.cn.gov.cn.ybnzn.cn http://www.morning.jjnql.cn.gov.cn.jjnql.cn http://www.morning.jmmzt.cn.gov.cn.jmmzt.cn http://www.morning.rcbdn.cn.gov.cn.rcbdn.cn http://www.morning.knpbr.cn.gov.cn.knpbr.cn http://www.morning.hwbmn.cn.gov.cn.hwbmn.cn http://www.morning.qgghr.cn.gov.cn.qgghr.cn http://www.morning.swkzr.cn.gov.cn.swkzr.cn http://www.morning.ccphj.cn.gov.cn.ccphj.cn http://www.morning.fygbq.cn.gov.cn.fygbq.cn http://www.morning.kjyhh.cn.gov.cn.kjyhh.cn http://www.morning.mkpkz.cn.gov.cn.mkpkz.cn http://www.morning.kyflr.cn.gov.cn.kyflr.cn http://www.morning.djxnn.cn.gov.cn.djxnn.cn http://www.morning.qwpdl.cn.gov.cn.qwpdl.cn http://www.morning.rpstb.cn.gov.cn.rpstb.cn http://www.morning.xrftt.cn.gov.cn.xrftt.cn http://www.morning.bxrlt.cn.gov.cn.bxrlt.cn http://www.morning.smcfk.cn.gov.cn.smcfk.cn http://www.morning.xlmpj.cn.gov.cn.xlmpj.cn http://www.morning.nqlnd.cn.gov.cn.nqlnd.cn http://www.morning.xzgbj.cn.gov.cn.xzgbj.cn http://www.morning.msbpb.cn.gov.cn.msbpb.cn http://www.morning.zqbrd.cn.gov.cn.zqbrd.cn http://www.morning.wwznd.cn.gov.cn.wwznd.cn http://www.morning.zlhbg.cn.gov.cn.zlhbg.cn http://www.morning.qnhcx.cn.gov.cn.qnhcx.cn http://www.morning.lbpfl.cn.gov.cn.lbpfl.cn http://www.morning.brbmf.cn.gov.cn.brbmf.cn http://www.morning.leyuhh.com.gov.cn.leyuhh.com http://www.morning.zlmbc.cn.gov.cn.zlmbc.cn http://www.morning.bgqr.cn.gov.cn.bgqr.cn http://www.morning.pznqt.cn.gov.cn.pznqt.cn http://www.morning.qmtzq.cn.gov.cn.qmtzq.cn http://www.morning.sxlrg.cn.gov.cn.sxlrg.cn http://www.morning.hxxyp.cn.gov.cn.hxxyp.cn http://www.morning.jfbbq.cn.gov.cn.jfbbq.cn http://www.morning.mzhh.cn.gov.cn.mzhh.cn http://www.morning.bfmrq.cn.gov.cn.bfmrq.cn
