python实现leetcode之146. LRU 缓存机制
2021-10-16 本文已影响0人
深圳都这么冷
解题思路
使用两个字典,删除的时候是O(N),效率不是很高,可以考虑使用平衡二叉树改进
146. LRU 缓存机制
代码
class LRUCache(object):
def __init__(self, capacity):
"""
:type capacity: int
"""
self.seq = 0
self.capacity = capacity
self.cache = {}
self.lifetime = {}
def get(self, key):
"""
:type key: int
:rtype: int
"""
v = self.cache.get(key, -1)
if v != -1:
self.lifetime[key] = self.seq
self.seq += 1
return v
def put(self, key, value):
"""
:type key: int
:type value: int
:rtype: None
"""
self.cache[key] = value
self.lifetime[key] = self.seq
self.seq += 1
if len(self.cache) > self.capacity:
# 删除老的项
oldest_key, seq = None, 0
for k, age in self.lifetime.items():
if oldest_key is None:
oldest_key, seq = k, age
elif age < seq:
oldest_key, seq = k, age
self.cache.pop(oldest_key)
self.lifetime.pop(oldest_key)
# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)
效果图