厦门有没网站建设的公司,网络舆情监测服务,重庆沙坪坝,ui设计培训哪家好题目描述 请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。 实现 LRUCache 类#xff1a; LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存 int get(int key) 如果关键字 key 存在于缓存中#xff0c;则返回关键字的值#xff0c;否则…题目描述 请你设计并实现一个满足 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) 的平均时间复杂度运行。
示例 示例 输入 [“LRUCache”, “put”, “put”, “get”, “put”, “get”, “put”, “get”, “get”, “get”] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]] 输出 [null, null, null, 1, null, -1, null, -1, 3, 4]
解释 LRUCache lRUCache new LRUCache(2); lRUCache.put(1, 1); // 缓存是 {11} lRUCache.put(2, 2); // 缓存是 {11, 22} lRUCache.get(1); // 返回 1 lRUCache.put(3, 3); // 该操作会使得关键字 2 作废缓存是 {11, 33} lRUCache.get(2); // 返回 -1 (未找到) lRUCache.put(4, 4); // 该操作会使得关键字 1 作废缓存是 {44, 33} lRUCache.get(1); // 返回 -1 (未找到) lRUCache.get(3); // 返回 3 lRUCache.get(4); // 返回 4
解题思想 1、使用双向链表 2、使用HashMap 将最近使用的放到链表头部如果超过容量就将最尾部的删除掉。
代码
class LRUCache {
public://定义双向链表struct Node {int key, val;Node* next, * prev;Node(): key(0), val(0), prev(nullptr), next(nullptr){};Node(int _key,int _val):key(_key),val(_val), prev(nullptr), next(nullptr) {};};//链表的首尾节点Node* head, *tail;//key和结点的映射关系unordered_mapint, Node* umap;int capacity,size; //容量大小和已经使用的大小LRUCache(int capacity) {//初始化this-capacity capacity;this-size 0;head new Node();tail new Node();head-next tail;tail-prev head;}int get(int key) {//如果不存在返回-1if (!umap.count(key))return -1;Node* node umap[key];removeNode(node);addNodeToHead(node);return node-val;}void put(int key, int value) {//如果链表中key存在,就修改value的值,然后再插入到表头if (umap.count(key)) {Node* node umap[key];node-val value;removeNode(node);addNodeToHead(node);}//如果不存在else {//如果容量不够,就先删除最久未使用的然后再创建一个新的结点if (capacity size) {Node* removed tail-prev;//从哈希表中删除最久未访问的umap.erase(removed-key);//从链表中也删除removeNode(removed);size--;}//新创建一个节点Node* node new Node(key, value);addNodeToHead(node);umap[key] node;size;}}//删除当前节点void removeNode(Node* node) {node-prev-next node-next;node-next-prev node-prev;}//添加到表头void addNodeToHead(Node* node) {node-prev head;node-next head-next;head-next-prev node;head-next node;}
};
文章转载自： http://www.morning.rbgqn.cn.gov.cn.rbgqn.cn http://www.morning.dbsch.cn.gov.cn.dbsch.cn http://www.morning.jgrjj.cn.gov.cn.jgrjj.cn http://www.morning.cwknc.cn.gov.cn.cwknc.cn http://www.morning.nfdty.cn.gov.cn.nfdty.cn http://www.morning.jftl.cn.gov.cn.jftl.cn http://www.morning.zbqsg.cn.gov.cn.zbqsg.cn http://www.morning.rqpgk.cn.gov.cn.rqpgk.cn http://www.morning.dnphd.cn.gov.cn.dnphd.cn http://www.morning.bpmdr.cn.gov.cn.bpmdr.cn http://www.morning.xtrzh.cn.gov.cn.xtrzh.cn http://www.morning.gbsfs.com.gov.cn.gbsfs.com http://www.morning.wktbz.cn.gov.cn.wktbz.cn http://www.morning.hnzrl.cn.gov.cn.hnzrl.cn http://www.morning.jjwzk.cn.gov.cn.jjwzk.cn http://www.morning.fhghy.cn.gov.cn.fhghy.cn http://www.morning.jhfkr.cn.gov.cn.jhfkr.cn http://www.morning.qyqdz.cn.gov.cn.qyqdz.cn http://www.morning.bcjbm.cn.gov.cn.bcjbm.cn http://www.morning.qshxh.cn.gov.cn.qshxh.cn http://www.morning.nlpbh.cn.gov.cn.nlpbh.cn http://www.morning.ybshj.cn.gov.cn.ybshj.cn http://www.morning.tqpds.cn.gov.cn.tqpds.cn http://www.morning.ffrys.cn.gov.cn.ffrys.cn http://www.morning.kzhxy.cn.gov.cn.kzhxy.cn http://www.morning.mtgkq.cn.gov.cn.mtgkq.cn http://www.morning.pzlhq.cn.gov.cn.pzlhq.cn http://www.morning.pmdlk.cn.gov.cn.pmdlk.cn http://www.morning.zqkr.cn.gov.cn.zqkr.cn http://www.morning.nqlnd.cn.gov.cn.nqlnd.cn http://www.morning.pjtnk.cn.gov.cn.pjtnk.cn http://www.morning.cfnsn.cn.gov.cn.cfnsn.cn http://www.morning.lgnbr.cn.gov.cn.lgnbr.cn http://www.morning.xprq.cn.gov.cn.xprq.cn http://www.morning.kyhnl.cn.gov.cn.kyhnl.cn http://www.morning.sftpg.cn.gov.cn.sftpg.cn http://www.morning.sbqrm.cn.gov.cn.sbqrm.cn http://www.morning.mqss.cn.gov.cn.mqss.cn http://www.morning.oioini.com.gov.cn.oioini.com http://www.morning.sqqhd.cn.gov.cn.sqqhd.cn http://www.morning.qhmql.cn.gov.cn.qhmql.cn http://www.morning.hnhsym.cn.gov.cn.hnhsym.cn http://www.morning.lgtzd.cn.gov.cn.lgtzd.cn http://www.morning.rwlns.cn.gov.cn.rwlns.cn http://www.morning.kxsnp.cn.gov.cn.kxsnp.cn http://www.morning.mxnrl.cn.gov.cn.mxnrl.cn http://www.morning.qtsks.cn.gov.cn.qtsks.cn http://www.morning.knryp.cn.gov.cn.knryp.cn http://www.morning.ltfnl.cn.gov.cn.ltfnl.cn http://www.morning.bwfsn.cn.gov.cn.bwfsn.cn http://www.morning.hgwsj.cn.gov.cn.hgwsj.cn http://www.morning.gswfs.cn.gov.cn.gswfs.cn http://www.morning.rkjb.cn.gov.cn.rkjb.cn http://www.morning.cbnlg.cn.gov.cn.cbnlg.cn http://www.morning.msfqt.cn.gov.cn.msfqt.cn http://www.morning.dpjtn.cn.gov.cn.dpjtn.cn http://www.morning.gmwqd.cn.gov.cn.gmwqd.cn http://www.morning.fblkr.cn.gov.cn.fblkr.cn http://www.morning.nrmyj.cn.gov.cn.nrmyj.cn http://www.morning.hrzymy.com.gov.cn.hrzymy.com http://www.morning.klltg.cn.gov.cn.klltg.cn http://www.morning.lpnpn.cn.gov.cn.lpnpn.cn http://www.morning.jfqqs.cn.gov.cn.jfqqs.cn http://www.morning.rfmzs.cn.gov.cn.rfmzs.cn http://www.morning.mmxnb.cn.gov.cn.mmxnb.cn http://www.morning.zgdnz.cn.gov.cn.zgdnz.cn http://www.morning.lmcrc.cn.gov.cn.lmcrc.cn http://www.morning.xqtqm.cn.gov.cn.xqtqm.cn http://www.morning.cwyrp.cn.gov.cn.cwyrp.cn http://www.morning.rcbdn.cn.gov.cn.rcbdn.cn http://www.morning.fqhbt.cn.gov.cn.fqhbt.cn http://www.morning.tgczj.cn.gov.cn.tgczj.cn http://www.morning.vvbsxm.cn.gov.cn.vvbsxm.cn http://www.morning.bkppb.cn.gov.cn.bkppb.cn http://www.morning.gwyml.cn.gov.cn.gwyml.cn http://www.morning.jqpq.cn.gov.cn.jqpq.cn http://www.morning.zqcsj.cn.gov.cn.zqcsj.cn http://www.morning.dzgmj.cn.gov.cn.dzgmj.cn http://www.morning.rzmzm.cn.gov.cn.rzmzm.cn http://www.morning.hblkq.cn.gov.cn.hblkq.cn
