Python solution using build-in list type as LinkedList, slow but accepted


  • 0
    Z
    class Pair(object):
    
        def __init__(self, key, value):
            self.key = key
            self.value = value
    
    class LRUCache(object):
    
        def __init__(self, capacity):
            self.capacity = capacity
            # map key to Pair
            self.mapper = {}
            # use python build-in list type as LinkedList
            self.cache = []
    
    
        def get(self, key):
            if key in self.mapper:
                pair = self.mapper[key]
                self.cache.remove(pair)
                self.cache.append(pair)
                return pair.value
            return -1
    
    
        def set(self, key, value):
            if key in self.mapper:
                pair = self.mapper[key]
                pair.value = value
                self.cache.remove(pair)
                self.cache.append(pair)
            else:
                if len(self.cache) == self.capacity:
                    del self.mapper[self.cache.pop(0).key]
                pair = Pair(key, value)
                self.cache.append(pair)
                self.mapper[key] = pair

Log in to reply
 

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