请你设计并实现一个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) 的平均时间复杂度运行
class LRUCache {
int count;
Map<Integer,Integer> map;
public LRUCache(int capacity) {
map=new LinkedHashMap<>();
count=capacity;
}
public int get(int key) {
if(map.containsKey(key)){
int value=map.get(key);
map.remove(key);
map.put(key,value);
return map.get(key);
}else{
return -1;
}
}
public void put(int key, int value) {
if(map.containsKey(key)){
map.remove(key);
map.put(key,value);
return;
}
if(count>0){
map.put(key,value);
count–;
}else{
int head=map.keySet().iterator().next();
map.remove(head);
map.put(key,value);
}
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/116065.html
