【文件属性】:
文件名称:javalruleetcode-LRU_cache:LRU_cache
文件大小:283KB
文件格式:ZIP
更新时间:2021-06-29 22:13:50
系统开源
java
lru
leetcode
LRU_cache
(Leetcode
146)
设计和实现最近最少使用
(LRU)
缓存的数据结构。
它应该支持以下操作:get
和
set。
get(key)
–
如果键存在于缓存中,则获取键的值(将始终为正),否则返回
-1。
set(key,
value)
–
如果键不存在,则设置或插入值。
当缓存达到其容量时,它应该在插入新项目之前使最近最少使用的项目无效。
跟进:你能在
O(1)
时间复杂度内完成这两个操作吗?
分析
LRU
缓存是将最近使用的项目保留在缓存中,并在缓存达到其容量时丢弃最近最少使用的项目。
因此,应按缓存中的“已用时间”按顺序保存项目。
我们需要跟踪每个项目的使用时间。
当我们调用
get(key)
函数时,除了返回它的值之外,我们还需要将其使用时间更新为最近的。
当我们调用
set(key,
value)
函数时,我们也需要更新它的使用时间。
我们可以使用由双链表实现的
Queue
来保存项目。
Queue
中的顺序代表“使用时间”的顺序。
例如,头部表示最近使用的项目,尾部表示最近最少使用的项目。
我们执行“删除”和“
【文件预览】:
LRU_cache-master
----date_structure.png(298KB)
----README.md(2KB)
----source_code()
--------cache_LRU.py(1KB)
--------test(4B)
--------cache_LRU.java(2KB)