Python Solution using dict and deque, 95%

  • 1

    we use a dict to store both the value and a time stamp.
    Every time we call get() or set(), the corresponding time-stamp will be updated.
    And we also use a deque to keep track of the operations. Every time we call get() or set(), we also append a (timestamp, key) ticket in the queue.
    Each ticket was pushed and popped once, so the average time is still O(1).

    from collections import deque
    class LRUCache(object):
        def __init__(self, capacity):
            self.capacity = capacity
            self.cache = {}
            self.q = deque()
            self.timestamp = 0
        def get(self, key):
            if key not in self.cache:
                return -1
            item = self.cache[key]
            item[1] = self.timestamp
            self.q.append((self.timestamp, key))
            self.timestamp += 1
            return item[0]
        def set(self, key, value):
            if key not in self.cache and len(self.cache) >= self.capacity:
                while True:
                    t, k = self.q.popleft()
                    if self.cache[k][1] == t:
            self.cache[key] = [value, self.timestamp]
            self.q.append((self.timestamp, key))        
            self.timestamp += 1

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.