Python Solution using dict and deque, 95%


  • 1
    A

    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:
                        break
                self.cache.pop(k)
                    
            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.