【每日一题】【模拟】2021年11月11日--LRU 缓存机制
2024-10-21 03:09:18
运用你所掌握的数据结构,设计和实现一个 LRU (最近最少使用) 缓存机制 。
实现 LRUCache 类:
LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1 。
void put(int key, int value) 如果关键字已经存在,则变更其数据值;如果关键字不存在,则插入该组「关键字-值」。当缓存容量达到上限时,它应该在写入新数据之前删除最久未使用的数据值,从而为新的数据值留出空间。
进阶:你是否可以在 O(1) 时间复杂度内完成这两种操作?
class LRUCache { public int cap;
public Map<Integer, Integer> map = new LinkedHashMap<Integer, Integer>();
public LRUCache(int capacity) {
this.cap = capacity;
} public int get(int key) {
if (map.containsKey(key)) {
int value = map.get(key);
map.remove(key);
map.put(key,value);
return value;
}
return -1;
} public void put(int key, int value) {
if (map.containsKey(key)) {
map.remove(key);
} else if (map.size() == cap) {
Iterator<Integer> iterator = map.keySet().iterator();
iterator.next();
iterator.remove();
}
map.put(key, value);
}
}
最新文章
- JAVA并发编程J.U.C学习总结
- Duplicate entry &#39;javajavajav&#39; for key &#39;username&#39;
- RakNet发送与接收数据
- 免费的网络扫描器-Advanced IP Scanner
- CodeVS 数轴染色
- Dynamics AX 2012 R2 在报表上显示和打印条码
- C# WinForm开发系列 - ListBox/ListView/Panel
- BeanDefinition的载入和解析
- Windows phone 之常用控件
- [Angular 2] Property Binding
- 记PHP面向对象编程
- 【从零开始搭建自己的.NET Core Api框架】(三)集成轻量级ORM——SqlSugar:3.1 搭建环境
- Win10系统电脑桌面图标没有了怎么办
- json转成java对象
- sencha touch 问题汇总
- ios开发 内测包添加测试UDID
- install ros-indigo-ecl-build
- 关于Unity中调试C#的方法
- unittest测试框架详谈及实操(三)
- 江铖:乳腺癌识别By AI