企业建站一条龙,衡阳企业网站,网站设计特色,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) 的平均时间复杂度运行。 由于我们在维护key-value键值对的同时还要注意它们的入队顺序所以用普通的Map肯定是不行的因为我亲身体验过 所以我们需要一个可以自动的维护顺序的数据结构才能处理本题所以LinikedHashMap肯定是最好的选择在我们在刷题的时候其实LinkedHashMap其实是不太常见的先在这里给大家科普一下 LinkedHashMap是一种集合类型它实现了Map接口并且通过双向链表维护了插入顺序或者访问顺序与常规的HashMap相比LinkedHashMap保持了键值对的插入顺序或访问顺序这使得它非常适合在按需要按照顺序访问元素的场景中使用
所以要手动的去构建一个结构体构造方法必不可少 LinkedHashMapInteger,Integer mapnew LinkedHashMap();private int capacity;//容量public LRUCache(int capacity) {this.capacitycapacity;} 在我们使用的过程中对于最新访问的key-value我们无需对其顺序进行改变但是如果我们去访问了一个比较使用时间过长的key-value那么每次都要对其键值进行删除增加这给代码带来非常差的可读性所以我们应该重新声明一个方法最近使用recently public void recently(int key){int valmap.get(key);map.remove(key);map.put(key,val);} 通过key值去获得value的值如果没有的话直接返回-1获取值也是一种操作证明这个key是刚使用过的所以直接调用函数recnetly() public int get(int key) {if(!map.containsKey(key)){return -1;}recently(key);return map.get(key);} 如果往进put的时候如果map的key的数量超过capacity,那就直接删除最早进来的key(很久没有使用的key值)直接提升为最近使用如果没有直接加入 public void put(int key, int value) {if(map.containsKey(key)){map.put(key,value);recently(key);return;}if(map.size()capacity){map.remove(map.keySet().iterator().next());}map.put(key,value);}
在这里给大家着重说明一下keySet().iterator().next()的功能 keySet():返回LinkedHashMap中的所有键的集合该方法将返回一个Set的对象其中包含所有的键 iterator():返回一个迭代器用于遍历集合中的元素在这种情况下我们获取到的是键集合的迭代器以便逐个访问键 next():迭代器的方法之一用于获取下一个元素由于我们希望获得第一个键所以该操作将返回集合中的第一个元素 用迭代器遍历集合当集合初始值不为空时遍历的过程中是不会抛出异常的因为集合遍历时用的fail-safe机制每次遍历的时候都是拿的原集合一个快照进行遍历如果当遍历的时候有人对集合进行增删结果可能就出现了问题
源码借鉴 LinkedHashMapInteger,Integer mapnew LinkedHashMap();private int capacity;public LRUCache(int capacity) {this.capacitycapacity;}public int get(int key) {if(!map.containsKey(key)){return -1;}recently(key);return map.get(key);}public void put(int key, int value) {if(map.containsKey(key)){map.put(key,value);recently(key);return;}if(map.size()capacity){map.remove(map.keySet().iterator().next());}map.put(key,value);}public void recently(int key){int valmap.get(key);map.remove(key);map.put(key,val);}
