O(1) Python Solution (Dict + Double Linked List)


  • 0
    class CacheEntry:
        
        def __init__(self, key=None, value=None, prev=None, next=None):
            self.key = key
            self.value = value
            self.prev = None
            self.next = None
    
        def __eq__(self, other):
            """Override the default Equals behavior"""
            if isinstance(other, self.__class__):
                return self.key == other.key
            return False
    
        def __repr__(self):
            return "(key={}, value={})".format(
                self.key,
                self.value)
    
    
    class LRUCache(object):
    
        def __init__(self, capacity):
            """
            :type capacity: int
            """
            self.count = 0
            self.capacity = capacity
            # dummy head and tail node
            self.head = CacheEntry()
            self.tail = CacheEntry()
            # Link dummy nodes
            self.head.next = self.tail
            self.tail.prev = self.head
            self.cache_map = {}
    
        def add_node(self, node):
            # Always add to the tail
            self.tail.prev.next = node
            node.next = self.tail
    
            node.prev = self.tail.prev
            self.tail.prev = node
    
        def remove_node(self, node):
            node.prev.next = node.next
            node.next.prev = node.prev
    
        def move_to_tail(self, node):
            self.remove_node(node)
            self.add_node(node)
    
        def get(self, key):
            """
            :type key: int
            :rtype: int
            """
    
            if key in self.cache_map:
                # Move to the tail
                node = self.cache_map[key]
                self.move_to_tail(node)
                return node.value
            else:
                return -1
    
        def put(self, key, value):
            """
            :type key: int
            :type value: int
            :rtype: void
            """
    
            if key in self.cache_map:
                node = self.cache_map[key]
                node.value = value
                self.move_to_tail(node)
            else:
                node = CacheEntry(key, value)
                if self.count < self.capacity:
                    self.add_node(node)
                    self.count += 1
                else:
                    # Remove the oldest node from head
                    del self.cache_map[self.head.next.key]
                    self.remove_node(self.head.next)
                    # Add new node to the tail
                    self.add_node(node)
    
                self.cache_map[key] = node
    

    Time complexity: O(1), Space complexity: O(capacity)


Log in to reply
 

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