- 921. Minimum Add to Make Parentheses Valid 使括号有效的最少添加
- 915. Partition Array into Disjoint Intervals 分割数组
- 932. Beautiful Array 漂亮数组
- 940. Distinct Subsequences II 不同的子序列 II
题目地址:https://leetcode.com/problems/lru-cache/
Design and implement a data structure for Least Recently Used (LRU)
cache. It should support the following operations: get
and put
.
Thecache is initialized with a positive
capacity.
Follow up: Could you do both operations in O(1)
time complexity?
Example:
LRUCache cache = new LRUCache( 2 /* capacity */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // returns 1
cache.put(3, 3); // evicts key 2
cache.get(2); // returns -1 (not found)
cache.put(4, 4); // evicts key 1
cache.get(1); // returns -1 (not found)
cache.get(3); // returns 3
cache.get(4); // returns 4
实现一个LRU,LRU全称是Least Recently Used,即最近最久未使用的意思。
LRU算法的设计原则是:如果一个数据在最近一段时间没有被访问到,那么在将来它被访问的可能性也很小。也就是说,当限定的空间已存满数据时,应当把最久没有被访问到的数据淘汰。
题目中给出了LRU的负载大小,当数据被用到的时候变成了最新被使用的,当存放的数据达到了容量上线,需要把最近未被使用的弹出。
如果看过Java的LinkedHashMap源码,大家都知道可以使用字典+双向链表来实现LRU。
其中双向链表的作用是用来维护使用的顺序的工具,把最近刚使用的放到链表最前面,一直未被使用的放到链表结尾,当达到容量的时候需要把链表结尾节点去除。
大家都知道链表的查找时间复杂度是O(N),题目要求用O(1)的时间复杂度,那么就需要高效的查找方法。我们使用字典来达到这个目的!把链表的每个节点按照{key: node}的方式放入字典里,这样就能通过key快速查到链表节点,从而对该节点进行修改。
综上,我们要对链表实现两个函数:
1、 把一个节点从链表中删除(这就是为什么选择双向链表的原因,方便找到前后节点);
2、 把一个节点放入链表的头部(需要一个不保存数据的root节点,其prev和next分别指向链表尾部和头部);
这个题中,链表节点需要同时保存key和value。我们通过key在字典找到该节点,返回其val;当要删除一直没被使用过的链表尾部节点时,我们也要从字典中删除它,因此需要知道其key。
python代码如下:
class ListNode:
def __init__(self, key, value):
self.key = key
self.value = value
self.prev = self
self.next = self
class LRUCache:
def __init__(self, capacity: int):
self.dic = dict()
self.capacity = capacity
self.size = 0
self.root = ListNode(0, 0)
def get(self, key: int) -> int:
if key in self.dic:
node = self.dic[key]
self.removeFromList(node)
self.insertIntoHead(node)
return node.value
else:
return -1
def put(self, key: int, value: int) -> None:
if key in self.dic:
node = self.dic[key]
self.removeFromList(node)
self.insertIntoHead(node)
node.value = value
else:
if self.size >= self.capacity:
self.removeFromTail()
self.size -= 1
node = ListNode(key, value)
self.insertIntoHead(node)
self.dic[key] = node
self.size += 1
def removeFromList(self, node):
if node == self.root: return
prev_node = node.prev
next_node = node.next
prev_node.next = next_node
next_node.prev = prev_node
node.prev = node.next = None
def insertIntoHead(self, node):
head_node = self.root.next
head_node.prev = node
node.prev = self.root
self.root.next = node
node.next = head_node
def removeFromTail(self):
if self.size == 0: return
tail_node = self.root.prev
del self.dic[tail_node.key]
self.removeFromList(tail_node)
# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64
参考资料:https://yikun.github.io/2015/04/03/%E5%A6%82%E4%BD%95%E8%AE%BE%E8%AE%A1%E5%AE%9E%E7%8E%B0%E4%B8%80%E4%B8%AALRU-Cache%EF%BC%9F/
2022
DDKK.COM 弟弟快看-教程,程序员编程资料站,版权归原作者所有
本文经作者:负雪明烛 授权发布,任何组织或个人未经作者授权不得转发
题目地址:https://leetcode.com/problems/lru-cache/ 题目描述 Design and implement a data structure for Least
我使用 redis 作为数据存储而不是缓存,但是设置了 maxmemory 限制,据我了解,maxmemory 指定了 redis 可以使用的 RAM,如果达到内存限制,它不应该将数据交换回磁盘。 我
假设redis 实例中的所有键都设置了过期时间,volatile-lru 和allkeys-lru 是相似的。但是,当删除 key 时,两者之间是否存在显着的性能差异? 奖励问题: 在配置了 allk
LRU-K 是一种缓存淘汰算法,旨在改进传统的LRU(Least Recently Used,最近最少使用)算法的性能。将其中高频的数据达到K次访问移入到另一个队列进行保护。 算法思想 LR
1.题目 请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。 实现 LRUCache 类: ① LRUCache(int capacity) 以正整数作为容量 capacity
如果 memcached 中的某个项目设置为永不过期,它是否免于 LRU 驱逐? 我见过的文档并没有清楚地描绘出哪个优先。在我看来,让 LRU 仅适用于过期 > 0 的项目是理想的(可能在内部非常复杂
当 memcache 中可用内存已满时,memcache 使用 LRU(最近使用的)算法来释放内存。 我的问题是 LRU 算法是否会删除在一段时间内(最近一次使用)未使用的条目而不是过期的条目? 即将
我在java中使用LRU缓存并覆盖了removeEldest。 @Override protected boolean removeEldestEntry (Map.Entry eldest) {
我前段时间已经发帖询问LRU缓存的良好设计(C++)。您可以在此处找到问题、答案和一些代码: Better understanding the LRU algorithm 我现在尝试对这段代码进行多线
我正在尝试使用这个 youtube video 自学 LRU 算法.在下面的示例 ( taken from here ) 中,为什么 0 被 3 代替。不应该是 4 被 3 代替,因为 4 是最少使用
我正在尝试使用 Caffeine 作为 LRU 缓存,因此首先添加的条目将首先被逐出。运行这段代码: final Cache map = Caffeine.newBuilder()
我对算法LRU有一点疑问。如果您有一个包含四个 block 的缓存,您需要多少位来实现该算法? 最佳答案 假设您指的是 4 路组相联缓存: “完美”的 LRU 本质上是按照使用顺序为每一行分配一个准确
我有两种类型的 Redis 键:post:{pid} 和 comment:{cid}。 我想存储最多 100 条记录的任一类型的缓存。 例如我有 100 条帖子记录和 50 条评论记录。当评论记录到来
我正在使用 Swift 构建一个应用程序,我想在我的应用程序中使用 LRU 缓存。我实现了一个简单的 LRUCache在 Swift 中,但后来我发现,由于它已经附带了 Dictionary 和 Ar
现在软件或者网页的并发量越来越大了,大量请求直接操作数据库会对数据库造成很大的压力,处理大量连接和请求就会需要很长时间,但是实际中百分之80的数据是很少更改的,这样就可以引入缓存来进行读取,减少数据
我有一些看起来像这样的代码: from functools import lru_cache @lru_cache() def get_cheese(type): print('{}? We\
我有一个规范,我试图定义一个 LRU 缓存系统,我遇到的一个问题是如何从结构键/值对(基本上是字典或哈希映射)中删除值其他语言)。 到目前为止,这是规范本身(不完整): EXTENDS Integer
如何使用 Erlang 实现 LRU 缓存? LRU Cache Wiki 最受关注的 Github 项目是 fogfish/cache ,但分段表不太适合我的数据。 barrel-db/erlang
我正在制作一个 Android 应用程序,其中有带有缩略图的新闻文章。这些缩略图从网络加载并存储在 LruCache 中,其中 URL 作为键,位图作为值。 private LruCache tCac
这个问题已经有答案了: How would you implement an LRU cache in Java? (21 个回答) 已关闭 5 年前。 我想仅使用 Java 内置的数据结构在 Jav
我是一名优秀的程序员,十分优秀!