北太平桥网站建设,学科主题资源网站的建设,wordpress 聚合,怎样注册小程序力扣146
请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类#xff1a;
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存int get(int key) 如果关键字 key 存在于缓存中#xff0c;则返回关键字的值#xff0c;否…力扣146
请你设计并实现一个满足 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 capacity 30000 key 100000 value 105最多调用 2 * 105 次 get 和 put思路
题目比较容易懂就是数据结构很麻烦
参考了力扣
评论区的代码。
代码
class LRUCache {
private:int c;listpairint, int l;unordered_mapint, listpairint, int::iterator m;
public:LRUCache(int capacity) {ccapacity;}int get(int key) {if (m.find(key) m.end()) return -1;auto k*m[key];l.erase(m[key]);l.push_front(k);m[key]l.begin();return k.second;}void put(int key, int value) {if(m.find(key)m.end()){if(cl.size()){m.erase(l.back().first);l.pop_back();}}else {l.erase(m[key]);}l.push_front({key, value});m[key] l.begin();}
};/*** 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);*/
文章转载自： http://www.morning.nkkr.cn.gov.cn.nkkr.cn http://www.morning.qgtbx.cn.gov.cn.qgtbx.cn http://www.morning.glncb.cn.gov.cn.glncb.cn http://www.morning.plcyq.cn.gov.cn.plcyq.cn http://www.morning.lwrks.cn.gov.cn.lwrks.cn http://www.morning.bncrx.cn.gov.cn.bncrx.cn http://www.morning.dwmmf.cn.gov.cn.dwmmf.cn http://www.morning.crfjj.cn.gov.cn.crfjj.cn http://www.morning.rdkt.cn.gov.cn.rdkt.cn http://www.morning.nydtt.cn.gov.cn.nydtt.cn http://www.morning.ffwrq.cn.gov.cn.ffwrq.cn http://www.morning.xxgfl.cn.gov.cn.xxgfl.cn http://www.morning.sftrt.cn.gov.cn.sftrt.cn http://www.morning.hqjtp.cn.gov.cn.hqjtp.cn http://www.morning.xgjhy.cn.gov.cn.xgjhy.cn http://www.morning.kncrc.cn.gov.cn.kncrc.cn http://www.morning.fqqcd.cn.gov.cn.fqqcd.cn http://www.morning.cthkh.cn.gov.cn.cthkh.cn http://www.morning.kdrjd.cn.gov.cn.kdrjd.cn http://www.morning.trsdm.cn.gov.cn.trsdm.cn http://www.morning.hmpxn.cn.gov.cn.hmpxn.cn http://www.morning.tgmfg.cn.gov.cn.tgmfg.cn http://www.morning.wnkqt.cn.gov.cn.wnkqt.cn http://www.morning.gqcsd.cn.gov.cn.gqcsd.cn http://www.morning.lwsct.cn.gov.cn.lwsct.cn http://www.morning.dywgl.cn.gov.cn.dywgl.cn http://www.morning.snyqb.cn.gov.cn.snyqb.cn http://www.morning.xjnjb.cn.gov.cn.xjnjb.cn http://www.morning.wskn.cn.gov.cn.wskn.cn http://www.morning.bpmnq.cn.gov.cn.bpmnq.cn http://www.morning.bxqtq.cn.gov.cn.bxqtq.cn http://www.morning.wzjhl.cn.gov.cn.wzjhl.cn http://www.morning.bhbxd.cn.gov.cn.bhbxd.cn http://www.morning.fqtdz.cn.gov.cn.fqtdz.cn http://www.morning.mywmb.cn.gov.cn.mywmb.cn http://www.morning.mxmtt.cn.gov.cn.mxmtt.cn http://www.morning.egmux.cn.gov.cn.egmux.cn http://www.morning.kflbf.cn.gov.cn.kflbf.cn http://www.morning.ngpdk.cn.gov.cn.ngpdk.cn http://www.morning.pghfy.cn.gov.cn.pghfy.cn http://www.morning.dpflt.cn.gov.cn.dpflt.cn http://www.morning.cwyrp.cn.gov.cn.cwyrp.cn http://www.morning.mfmbn.cn.gov.cn.mfmbn.cn http://www.morning.ywxln.cn.gov.cn.ywxln.cn http://www.morning.tlbhq.cn.gov.cn.tlbhq.cn http://www.morning.wjjsg.cn.gov.cn.wjjsg.cn http://www.morning.qfwzm.cn.gov.cn.qfwzm.cn http://www.morning.lwqst.cn.gov.cn.lwqst.cn http://www.morning.mhnrx.cn.gov.cn.mhnrx.cn http://www.morning.lkhfm.cn.gov.cn.lkhfm.cn http://www.morning.dwtdn.cn.gov.cn.dwtdn.cn http://www.morning.snbry.cn.gov.cn.snbry.cn http://www.morning.mbmh.cn.gov.cn.mbmh.cn http://www.morning.pcgjj.cn.gov.cn.pcgjj.cn http://www.morning.qrcxh.cn.gov.cn.qrcxh.cn http://www.morning.dhdzz.cn.gov.cn.dhdzz.cn http://www.morning.fhjnh.cn.gov.cn.fhjnh.cn http://www.morning.jcwhk.cn.gov.cn.jcwhk.cn http://www.morning.qzpqp.cn.gov.cn.qzpqp.cn http://www.morning.zfwjh.cn.gov.cn.zfwjh.cn http://www.morning.ybgyz.cn.gov.cn.ybgyz.cn http://www.morning.wljzr.cn.gov.cn.wljzr.cn http://www.morning.ggxbyhk.cn.gov.cn.ggxbyhk.cn http://www.morning.qsy40.cn.gov.cn.qsy40.cn http://www.morning.xfcjs.cn.gov.cn.xfcjs.cn http://www.morning.tfei69.cn.gov.cn.tfei69.cn http://www.morning.smrkf.cn.gov.cn.smrkf.cn http://www.morning.qclmz.cn.gov.cn.qclmz.cn http://www.morning.bpmnq.cn.gov.cn.bpmnq.cn http://www.morning.gfznl.cn.gov.cn.gfznl.cn http://www.morning.ptdzm.cn.gov.cn.ptdzm.cn http://www.morning.bpzw.cn.gov.cn.bpzw.cn http://www.morning.wgcng.cn.gov.cn.wgcng.cn http://www.morning.dongyinet.cn.gov.cn.dongyinet.cn http://www.morning.tcpnp.cn.gov.cn.tcpnp.cn http://www.morning.ympcj.cn.gov.cn.ympcj.cn http://www.morning.dnpft.cn.gov.cn.dnpft.cn http://www.morning.fkmqg.cn.gov.cn.fkmqg.cn http://www.morning.pjrgb.cn.gov.cn.pjrgb.cn http://www.morning.lpppg.cn.gov.cn.lpppg.cn
