Leetcode: 146. LRU Cache LRU缓存机制
发布日期:2021-09-14 15:33:20
浏览次数:8
分类:技术文章
本文共 1507 字,大约阅读时间需要 5 分钟。
LRU Cache LRU缓存机制
运用你所掌握的数据结构,设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作: 获取数据 get 和 写入数据 put 。
- 获取数据 get(key) - 如果密钥 (key) 存在于缓存中,则获取密钥的值(总是正数),否则返回 -1。
- 写入数据 put(key, value) -如果密钥不存在,则写入其数据值。当缓存容量达到上限时,它应该在写入新数据之前删除最近最少使用的数据值,从而为新的数据值留出空间。
你是否可以在 O(1) 时间复杂度内完成这两种操作?
示例:
LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );cache.put(1, 1);cache.put(2, 2);cache.get(1); // 返回 1cache.put(3, 3); // 该操作会使得密钥 2 作废cache.get(2); // 返回 -1 (未找到)cache.put(4, 4); // 该操作会使得密钥 1 作废cache.get(1); // 返回 -1 (未找到)cache.get(3); // 返回 3cache.get(4); // 返回 4
方法一:哈希表+双向链表
关于splice的使用方法l.splice(l.begin(), l, it->second);
将l中的由迭代器it->second指向的元素移到l.begin()处。也即将使用过的元素移到开头。 class LRUCache{ public: LRUCache(int capacity) { cap = capacity; } int get(int key) { // auto it = m.find(key); if (it == m.end()) return -1; l.splice(l.begin(), l, it->second); return it->second->second; } void put(int key, int value) { auto it = m.find(key); //若出现过元素,则擦除该元素 if (it != m.end()) l.erase(it->second); //元素放置到开头 l.push_front(make_pair(key, value)); m[key] = l.begin(); //当达到缓存容量将末尾的元素释放 if (m.size() > cap) { int k = l.rbegin()->first; l.pop_back(); m.erase(k); } } private: int cap; //双向链表:装着 (key, value) 元组 list> l; //哈希表:key 映射到 (key, value) 在 cache 中的位置 unordered_map >::iterator> m;};
转载地址:https://blog.csdn.net/weixin_42490152/article/details/101540060 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
很好
[***.229.124.182]2024年03月30日 16时55分44秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
软工视频—用户界面设计
2019-04-26
三种web服务器—Apache、Tomcat、IIS
2019-04-26
软工文档总结
2019-04-26
UML构成
2019-04-26
UML—用例图
2019-04-26
UML—静态图
2019-04-26
UML—行为图
2019-04-26
UML—交互图
2019-04-26
UML—实现图
2019-04-26
C#视频—C#基础(一)数据类型
2019-04-26
C#视频—C#基础(二)量的定义
2019-04-26
C#视频—C#基础(三)运算符+三大结构
2019-04-26
C#视频—继承
2019-04-26
C#视频—多态
2019-04-26
c#—OpenFileDialog(打开文件对话框)
2019-04-26
c#—如何借助windows media player控件编写播放器
2019-04-26
简单工厂模式和策略模式的比较
2019-04-26
简单工厂、工厂方法、抽象工厂模式
2019-04-26
单例模式
2019-04-26
组合模式
2019-04-26