请你设计一个LRU（最近最少使用）缓存约束的数据结构

╰半橙微兮° 2023-09-27 09:02 87阅读 0赞

请你设计并实现一个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);
> 
> \}
> 
> \}
> 
> \}

发表评论取消回复

表情：

评论列表（有 0 条评论，87人围观）

还没有评论，来说两句吧...

相关阅读

相关操作系统LRU算法(最近最少使用算法)

操作系统LRU算法(最近最少使用算法) ![在这里插入图片描述][b448a3e493bb4be9bc9aafc3ba8dfb72.png] 提交代码 //

太过爱你忘了你带给我的痛/ 2024年03月31日 14:47/ 0 赞/ 41 阅读

相关请你设计一个LRU（最近最少使用）缓存约束的数据结构

请你设计并实现一个LRU（最近最少使用）满足约束的数据结构。实现 `LRUCache` 类： `LRUCache(int capacity)` 以正整数作为容

╰半橙微兮°/ 2023年09月27日 09:02/ 0 赞/ 88 阅读

相关 LRU (最近最少使用页面置换算法) 的代码实现

阅读之前推荐先阅读博主关于LinkedHashMap的文章，传送地址：[LinkedHashMap源码分析，基于JDK1.8逐行分析][LinkedHashMap_JDK1.8

不念不忘少年蓝@/ 2023年01月17日 08:26/ 0 赞/ 187 阅读

相关 LRU算法实现--最近最少使用

实现缓存要求： LinkedHashMap HashMap（保证查找操作为O(1)）双向Link（保证排序、新增操作为O

淡淡的烟草味﹌/ 2022年10月16日 09:56/ 0 赞/ 195 阅读

相关 Redis精通系列——LRU算法详述(Least Recently Used - 最近最少使用)

本文已收录于专栏 [❤️《Redis精通系列》❤️][Redis] 上千人点赞收藏，全套Redis学习资料，大厂必备技能！ --------------------

叁歲伎倆/ 2022年09月11日 15:30/ 0 赞/ 172 阅读

相关 LRU(最近最少使用页面置换算法)淘汰算法

什么是LRU算法? LRU是Least Recently Used的缩写，即最近最少使用页面置换算法，是为虚拟页式存储管理服务的。关于操作系统的内存管理，如何节省利用容量不

待我称王封你为后i/ 2022年08月13日 18:34/ 0 赞/ 198 阅读

相关 LRU (最近最少使用) 缓存机制:时间复杂度O（1）

/ Double Linked List 用了一个特别的双向的ListNode，有了head和tail，这样就大大加快了速度。

逃离我推掉我的手/ 2022年05月16日 14:43/ 0 赞/ 163 阅读

相关 LRU最少最近使用缓存策略

LRU（Least Recently Used）直译为“最近最少使用” 缓存的容量是有限的当缓存容量不足以存放需要缓存的新数据时，必须丢掉最不常用的缓存数据使用ha

曾经终败给现在/ 2022年02月05日 02:15/ 0 赞/ 234 阅读

相关 HashMap实现LRU（最近最少使用）缓存更新算法

最近阿里巴巴电话面试被问到了如何使用固定容量的HashMap，实现LRU算法。当时一脸懵逼，平时用HashMap也就用来快速存取数据而已，容量都是不限的。想了半天，想到对n

曾经终败给现在/ 2022年02月01日 19:45/ 0 赞/ 237 阅读

相关基于最少使用频次的LRU,LFU缓存淘汰算法

LFU(Least Frequently Used)即最近最不常用.看名字就知道是个基于访问频次的一种算法。以前写过几篇关于用python实现lru算法的模块，有兴趣的朋...

朱雀/ 2020年10月25日 08:12/ 0 赞/ 730 阅读