146. LRU Cache

Loading...LeetCode

这个设计实现不难，用queue来记录 use history 就行了，但题目里有个 follow-up：

Could you do both operations in O(1) time complexity?

用list.remove()肯定是 O(N) 的，所以看了下 solution 和 discuss 里面实现 O(1) 的方法。

一个是linked list, 问题核心是改变node在list里的位置，分解一下就是删除和插入两个操作，通过修改连接指针，double linked list 只需要 O(1) 来完成这两个操作（对比下，array 的remove/insert实际上是把后面的每个元素往前移一格。）

还有就是用collections.OrderedDict()，把 dict 和 queue 结合在一个对象里了（although I think it is not good idea to use OrderedDict in interview but whatever I learned a new thing），知道这个 built-in 数据结构的话就很简单，没啥好说的...

queue

class LRUCache:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = dict()
        self.usedQueue = collections.deque([])

    def get(self, key: int) -> int:
        if key not in self.cache: return -1
        self.usedQueue.remove(key)
        self.usedQueue.append(key)
        return self.cache[key]
        
        
    def put(self, key: int, value: int) -> None:
        if key in self.cache.keys():
            self.usedQueue.remove(key)
        elif len(self.cache) >= self.capacity:
            leastRecentlyUsed = self.usedQueue.popleft()
            self.cache.pop(leastRecentlyUsed)
        self.cache[key] = value
        self.usedQueue.append(key)


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

linked list

class Node:
    def __init__(self, k, v):
        self.key = k
        self.val= v
        self.prev = None
        self.next = None

        
class LRUCache:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}
        self.head = Node(0, 0)
        self.tail = Node(-1, -1)
        self.head.next = self.tail
        self.tail.prev = self.head

    def get(self, key: int) -> int:
        if key not in self.cache: return -1
        node = self.cache[key]        
        self.evict(node)
        self.push(node)
        return node.val
        

    def put(self, key: int, value: int) -> None:
        if key not in self.cache:
            if len(self.cache) >= self.capacity:
                node = self.head.next
                self.cache.pop(node.key)
                self.evict(node)
            self.cache[key] = Node(key, value)
            self.push(self.cache[key])
            return
        else:
            node = self.cache[key]
            self.evict(node)
            self.push(node)
            node.val = value
    
    def evict(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev
        
    def push(self, node):
        node.next = self.tail
        node.prev = self.tail.prev
        node.prev.next = node
        self.tail.prev = node
    
        


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

ordered dict

class LRUCache:

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

    def get(self, key: int) -> int:
        if key not in self.cache: return -1
        self.cache.move_to_end(key)
        return self.cache[key]
        
        
    def put(self, key: int, value: int) -> None:
        if key not in self.cache:
            if len(self.cache) >= self.capacity:
                self.cache.popitem(last=False) # last=True, LIFO; last=False, FIFO. We want to remove in FIFO fashion. 
        else: self.cache.move_to_end(key) # if key in cache, move it to the end
        self.cache[key] = value