【哈希表】Leecode-146. LRU 缓存

【题目】

【题解】

题解1：

• 思路

        每次使用元素将元素拿到栈顶，如果插入导致栈溢出则删除栈底元素

• 复杂度

         时间复杂度：O(1)，空间复杂度：O(n)

• 代码

class LRUCache:

    def __init__(self, capacity: int):
        self.cache = collections.defaultdict()
        self.capacity = capacity

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        ret = self.cache.get(key)
        self.cache.pop(key)
        self.cache[key] = ret
        return ret


    def put(self, key: int, value: int) -> None:
        if len(self.cache)<=self.capacity:
            if key not in self.cache:
                self.cache[key] = value
            else:
                self.cache.pop(key)
                self.cache[key] = value 
        else:
            self.cache.pop(list(self.cache.keys())[0])
            self.cache[key] = value





# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)