首页 > 其他分享 >146.LRU 缓存

146.LRU 缓存

时间:2022-11-10 18:35:30浏览次数:52  
标签:146 缓存 get int 关键字 LRU put lRUCache

请你设计并实现一个满足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) 的平均时间复杂度运行。

示例:

输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4
解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废,缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废,缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

提示:

  • 1 <= capacity <= 3000
  • 0 <= key <= 10000
  • 0 <= value <= 105
  • 最多调用 2 * 105 次 get 和 put

 

标签:146,缓存,get,int,关键字,LRU,put,lRUCache
From: https://www.cnblogs.com/icyyyy/p/16877997.html

相关文章

  • Guava LoadingCache本地缓存的正确使用姿势——异步加载
    1.【背景】AB实验SDK耗时过高同事在使用我写的实验平台sdk之后,吐槽耗时太高,获取实验数据分流耗时达到700ms,严重影响了主业务流程的执行2.【分析】缓存为何不管用我记......
  • SpringBoot整合Ehcache缓存(二十二)
    二八佳人体似酥,腰间仗剑斩愚夫。虽然不见人头落,暗里教君骨髓枯。上一章简单介绍了SpringBoot整合Cache缓存技术(二十一),如果没有看过,​​请观看上一章​​一.Ehcache关于......
  • 用java做一个内存缓存
    项目中对接第三方系统需要先获取认证token后,才能调用其他接口,token的有效期(固定为1小时),如果使用redis来做,十分简单,设置redis缓存加上1个小时有效期就可以解决。现在需要自......
  • 浏览器的缓存机制
    浏览器的缓存机制(强缓存、协商缓存)先来粗略的概念:什么是浏览器的缓存机制浏览器的缓存机制就是把一个请求过的web资源(例如:html页面、图片、js、数据等)拷贝一份副......
  • 浅谈内存缓存和硬盘缓存
    内存缓存(frommemorycache)和硬盘缓存(fromdiskcache)内存缓存(frommemorycache):内存缓存具有两个特点,分别是快速读取和时效性:1、快速读取:内存缓存会将编译解析后......
  • Redis缓存
    认识缓存缓存更新策略缓存穿透缓存击穿缓存雪崩  认识缓存缓存的作用1,降低后端负载2,提高服务于相应速度缓存的成本1.开发成本 2,运维成本3,一致性成本......
  • ZooKeeper : Curator框架之数据缓存与监听CuratorCache
    CuratorCache​​CuratorCache​​​会试图将来自节点的数据保存在本地缓存中。可以缓存指定的单个节点,也可以缓存以指定节点为根的整个子树(默认缓存方案)。可以给​​Curat......
  • vue项目中禁用浏览器缓存配置案例
    项目发布新版本,部署线上后用户浏览器需要清理缓存1.public文件夹中修改index.html文件meta配置<metahttp-equiv="Cache-Control"content="no-cache,no-store,must-......
  • 手写本地缓存实战2—— 打造正规军,构建通用本地缓存框架
    大家好,又见面了。本文是笔者作为掘金技术社区签约作者的身份输出的缓存专栏系列内容,将会通过系列专题,讲清楚缓存的方方面面。如果感兴趣,欢迎关注以获取后续更新。村......
  • 一本通 1469:似乎在梦中见过的样子
    对于字符串S,求有多少合法子串(该子串形式为ABA,len(B)>=1,len(A)>=K) lenS=15e3 谁能想到这题是暴力n^2直接n^2枚举l,r,预处理出kmp的next[],逐个判断 ......