python实现leetcode之146. LRU 缓存机制

解题思路

使用两个字典，删除的时候是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)