LeetCode - LRU怎么将书架上的旧书完美淘汰呢
2024-08-30 10:27:00
你有一排书架,有空时会拿些书来看,经常性会买些新书。无奈书架容量有限,当新买的书放不下时,需要一个策略将旧书淘汰。
LRU(最近最少使用)缓存淘汰机制正合适。
1)新买的书放在最左侧。
2)最近常看的书也放在最左侧。
久而久之,越往右边的书越是长时间没看,当有新书时,就从右侧淘汰起。Perfect。
下面一起来动手实现这个算法。附加条件只有一个,要在 O(1) 的时间复杂度内完成操作。
查找操作能在O(1)的数据结构: 哈希
增、删除操作能在O(1)的数据结构:链表
所以考虑哈希 + 单链 或哈希 +双链表。不过现实中,双链表的使用场景远多于单链表。
原因大家仔细考虑下,欢迎留言
class ListNode:
def __init__(self, key = None, value =None):
self.key = key
self.value = value
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.hashmap = {}
# 哨兵
self.head = ListNode()
self.tail = ListNode()
self.head.next = self.tail
self.tail.prev = self.head
def move_node_to_tail(self, key):
node = self.hashmap[key]
node.prev.next = node.next
node.next.prev = node.prev
node.prev = self.tail.prev
node.next = self.tail
self.tail.prev.next = node
self.tail.prev = node
def get(self,key:int) -> int:
if key in self.hashmap:
self.move_node_to_tail(key)
res = self.hashmap.get(key, -1)
if res == -1:
return res
else:
return res.value
def put(self, key:int, value:int)->int:
if key in self.hashmap:
self.hashmap[key].value= value
self.move_node_to_tail(key)
return
if len(self.hashmap) == self.capacity:
self.hashmap.pop(self.head.next.key)
self.head.next = self.head.next.next
self.head.next.prev = self.head
new = ListNode(key,value)
self.hashmap[key] = new
new.prev = self.tail.prev
new.next = self.tail
self.tail.prev.next = new
self.tail.prev = new
最新文章
- JavaScript基本语法(四)
- Nagios配置文件详解
- H5之contenteditable
- 快速理解Kafka分布式消息队列框架
- onTouch与onClick事件的关系
- ubuntu 设置显示器的亮度
- SQL优化之索引
- java基础学习总结四(控制语句<;顺序、选择、循环>;、方法)
- java整合flex
- java基础:数组的复制
- ldap数据库--ODSEE--复制协议
- C. Kyoya and Colored Balls(Codeforces Round #309 (Div. 2))
- win7局域网共享文件
- 消息中间件activemq的使用场景介绍(结合springboot的示例)
- Centos6.5 pppoe-server
- Python matplotlib.pyplot
- 恢复Windows 10自带的微软正黑字体
- linux学习笔记整理(七)
- Activiti reassign task to another user
- MySQL记录-Lost Connect MySQL Server during query解决方案