无锡企业网站制作哪家好,包头网站建设价格,h5页面图片,企业信用信息查询网官网相关题目 146. LRU 缓存
要让 put 和 get ⽅法的时间复杂度为 O(1)#xff0c;我们可以总结出 cache 这个数据结构必要的条件#xff1a; 1、显然 cache 中的元素必须有时序#xff0c;以区分最近使⽤的和久未使⽤的数据#xff0c;当容量满了之后要删除最久未使⽤的那个元…相关题目 146. LRU 缓存
要让 put 和 get ⽅法的时间复杂度为 O(1)我们可以总结出 cache 这个数据结构必要的条件 1、显然 cache 中的元素必须有时序以区分最近使⽤的和久未使⽤的数据当容量满了之后要删除最久未使⽤的那个元素腾位置。 2、我们要在 cache 中快速找某个 key 是否已存在并得到对应的 val。 3、每次访问 cache 中的某个 key需要将这个元素变为最近使⽤的也就是说 cache 要⽀持在任意位置快速插⼊和删除元素。
哈希表查找快但是数据⽆固定顺序链表有顺序之分插⼊删除快但是查找慢所以结合⼆者的⻓处可以形成⼀种新的数据结构哈希链表 LinkedHashMap
在Python中可以使用collections模块中的OrderedDict类来实现类似于Java中LinkedHashMap的功能。
本文最后还提供了一种 结合双向链表和哈希表的 从零开始的实现供参考。
// 使用 LinkedHashMap 实现
class LRUCache {int cap;LinkedHashMapInteger, Integer cache new LinkedHashMap();public LRUCache(int capacity) {this.cap capacity;}public int get(int key) {if (!cache.containsKey(key)) {return -1;}// 将 key 变为最近使⽤makeRecently(key);return cache.get(key);}public void put(int key, int val) {if (cache.containsKey(key)) {// 修改 key 的值cache.put(key, val);// 将 key 变为最近使⽤makeRecently(key);return;}if (cache.size() this.cap) {// 链表头部就是最久未使⽤的 keyint oldestKey cache.keySet().iterator().next();cache.remove(oldestKey);}// 将新的 key 添加链表尾部cache.put(key, val);}private void makeRecently(int key) {int val cache.get(key);// 删除 key重新插⼊到队尾cache.remove(key);cache.put(key, val);}
}
# 使用 OrderedDict 实现
from collections import OrderedDictclass LRUCache:def __init__(self, capacity: int):self.cc capacityself.d OrderedDict()def get(self, key: int) - int:if key in self.d:self.d.move_to_end(key)return self.d[key]return -1def put(self, key: int, value: int) - None:if key in self.d:del self.d[key]self.d[key] valueif len(self.d) self.cc:self.d.popitem(lastFalse)
# 手撸LRU算法结合双向链表和哈希表LinkedHashMap
# 先定义双向链表节点
class DoubleListNodeLRU:next, last None, Nonedef __init__(self, k, v):self.k kself.v vclass NodeLRU:head, tail None, Nonesize Nonedef __init__(self):# head tail 为 头尾虚拟节点self.head DoubleListNodeLRU(0, 0)self.tail DoubleListNodeLRU(0, 0)self.head.next self.tailself.tail.last self.headself.size 0# 链表尾部添加节点 时间 O(1)def addLast(self, x: DoubleListNodeLRU):x.last self.tail.lastx.next self.tailself.tail.last.next xself.tail.last xself.size 1# 删除链表中的 x 节点x ⼀定存在# 由于是双链表且给的是⽬标Node节点时间O(1)def remove(self, x: DoubleListNodeLRU):x.last.next x.nextx.next.last x.lastself.size - 1# 删除链表中第⼀个节点并返回该节点时间 O(1)def removeFirst(self):if self.head.next self.tail:return Nonefirst self.head.nextself.remove(first)return firstclass LRUCache:def __init__(self, capacity: int):self.cap capacity# key - node(key, val)self.map dict()self.cache NodeLRU()# 将某个 key 提升为最近使⽤的def makeRecently(self, k):node self.map.get(k)self.cache.remove(node)self.cache.addLast(node)# 添加最近使⽤的元素def addRecently(self, k, v):node DoubleListNodeLRU(k, v)self.cache.addLast(node)self.map[k] node# 删除某⼀个 keydef deletekey(self, k):node self.map[k]self.map.pop(k)self.cache.remove(node)def removeLeastRecently(self):deleteNode self.cache.removeFirst()deletekey deleteNode.kself.map.pop(deletekey)def get(self, k):if k not in self.map:return -1self.makeRecently(k)return self.map.get(k).vdef put(self, k, v):if k in self.map:self.deletekey(k)self.addRecently(k, v)returnif self.cache.size self.cap:self.removeLeastRecently()self.addRecently(k, v)
