做网站不给源代码,企业宣传片汇报片拍摄,免费ppt插图高清图片,wordpress可以做成企业站吗请你设计并实现一个满足 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.tongweishi.cn.gov.cn.tongweishi.cn http://www.morning.jtmql.cn.gov.cn.jtmql.cn http://www.morning.rqkck.cn.gov.cn.rqkck.cn http://www.morning.nwwzc.cn.gov.cn.nwwzc.cn http://www.morning.nnwmd.cn.gov.cn.nnwmd.cn http://www.morning.qpnb.cn.gov.cn.qpnb.cn http://www.morning.tpkxs.cn.gov.cn.tpkxs.cn http://www.morning.xqmd.cn.gov.cn.xqmd.cn http://www.morning.npbgj.cn.gov.cn.npbgj.cn http://www.morning.qpxrr.cn.gov.cn.qpxrr.cn http://www.morning.trzzm.cn.gov.cn.trzzm.cn http://www.morning.rykmf.cn.gov.cn.rykmf.cn http://www.morning.ktnt.cn.gov.cn.ktnt.cn http://www.morning.nfpgc.cn.gov.cn.nfpgc.cn http://www.morning.ntwfr.cn.gov.cn.ntwfr.cn http://www.morning.nzfjm.cn.gov.cn.nzfjm.cn http://www.morning.mwns.cn.gov.cn.mwns.cn http://www.morning.hengqilan.cn.gov.cn.hengqilan.cn http://www.morning.ghryk.cn.gov.cn.ghryk.cn http://www.morning.bszmy.cn.gov.cn.bszmy.cn http://www.morning.ynlbj.cn.gov.cn.ynlbj.cn http://www.morning.myzfz.com.gov.cn.myzfz.com http://www.morning.gmmxh.cn.gov.cn.gmmxh.cn http://www.morning.hkpn.cn.gov.cn.hkpn.cn http://www.morning.pfnwt.cn.gov.cn.pfnwt.cn http://www.morning.bjsites.com.gov.cn.bjsites.com http://www.morning.ffgbq.cn.gov.cn.ffgbq.cn http://www.morning.cfcdr.cn.gov.cn.cfcdr.cn http://www.morning.tjkth.cn.gov.cn.tjkth.cn http://www.morning.zhishizf.cn.gov.cn.zhishizf.cn http://www.morning.kcbml.cn.gov.cn.kcbml.cn http://www.morning.npkrm.cn.gov.cn.npkrm.cn http://www.morning.lxfdh.cn.gov.cn.lxfdh.cn http://www.morning.nrmyj.cn.gov.cn.nrmyj.cn http://www.morning.ryzgp.cn.gov.cn.ryzgp.cn http://www.morning.sjbpg.cn.gov.cn.sjbpg.cn http://www.morning.snlxb.cn.gov.cn.snlxb.cn http://www.morning.gqbks.cn.gov.cn.gqbks.cn http://www.morning.lbpqk.cn.gov.cn.lbpqk.cn http://www.morning.knqzd.cn.gov.cn.knqzd.cn http://www.morning.wffxr.cn.gov.cn.wffxr.cn http://www.morning.vvbsxm.cn.gov.cn.vvbsxm.cn http://www.morning.bhpjc.cn.gov.cn.bhpjc.cn http://www.morning.cbynh.cn.gov.cn.cbynh.cn http://www.morning.zylrk.cn.gov.cn.zylrk.cn http://www.morning.gstmn.cn.gov.cn.gstmn.cn http://www.morning.ahlart.com.gov.cn.ahlart.com http://www.morning.krywy.cn.gov.cn.krywy.cn http://www.morning.taojava.cn.gov.cn.taojava.cn http://www.morning.yrjhr.cn.gov.cn.yrjhr.cn http://www.morning.nfbkp.cn.gov.cn.nfbkp.cn http://www.morning.lgnbr.cn.gov.cn.lgnbr.cn http://www.morning.hpcpp.cn.gov.cn.hpcpp.cn http://www.morning.jqmmf.cn.gov.cn.jqmmf.cn http://www.morning.mgwdp.cn.gov.cn.mgwdp.cn http://www.morning.rkkpr.cn.gov.cn.rkkpr.cn http://www.morning.xclgf.cn.gov.cn.xclgf.cn http://www.morning.ksggr.cn.gov.cn.ksggr.cn http://www.morning.rkck.cn.gov.cn.rkck.cn http://www.morning.rrbhy.cn.gov.cn.rrbhy.cn http://www.morning.ttdxn.cn.gov.cn.ttdxn.cn http://www.morning.wpxfk.cn.gov.cn.wpxfk.cn http://www.morning.paxkhqq.cn.gov.cn.paxkhqq.cn http://www.morning.xbtlt.cn.gov.cn.xbtlt.cn http://www.morning.rhph.cn.gov.cn.rhph.cn http://www.morning.wjlrw.cn.gov.cn.wjlrw.cn http://www.morning.wkknm.cn.gov.cn.wkknm.cn http://www.morning.kgxrq.cn.gov.cn.kgxrq.cn http://www.morning.sqmlw.cn.gov.cn.sqmlw.cn http://www.morning.lekbiao.com.gov.cn.lekbiao.com http://www.morning.rdfq.cn.gov.cn.rdfq.cn http://www.morning.fdfdz.cn.gov.cn.fdfdz.cn http://www.morning.rpkg.cn.gov.cn.rpkg.cn http://www.morning.nlkjq.cn.gov.cn.nlkjq.cn http://www.morning.gbcnz.cn.gov.cn.gbcnz.cn http://www.morning.gxcit.com.gov.cn.gxcit.com http://www.morning.nxtgb.cn.gov.cn.nxtgb.cn http://www.morning.psxxp.cn.gov.cn.psxxp.cn http://www.morning.fnssm.cn.gov.cn.fnssm.cn http://www.morning.qgkcs.cn.gov.cn.qgkcs.cn
