Clean Python solution with dict + doubly linked list (beats 99.15%)


  • 2
    A
    class Node(object):
    
        def __init__(self, key, val):
            self.val = val
            self.key = key
            self.next = None
            self.prev = None
    
    
    class LRUCache(object):
    
        def __init__(self, capacity):
            self.head = None
            self.tail = None
            self.capacity = capacity
            self.size = 0
            self.hashmap = {}
    
        def get(self, key):
            if key in self.hashmap:
                node = self.hashmap[key]
                self.delete(node)
                self.insert(node)
                return node.val
            else:
                return -1
            
        def set(self, key, val):
            if key not in self.hashmap:
                self.insert(Node(key, val))
            else:
                node = self.hashmap[key]
                node.val = val
                self.delete(node)
                self.insert(node)
        
        def insert(self, node):
            if self.size == self.capacity:
                self.delete(self.tail)
            if not self.head:
                self.head = node
                self.tail = node
            else:
                node.next = self.head
                self.head.prev = node
                self.head = node
            self.hashmap[node.key] = node
            self.size += 1
            
        def delete(self, node):
            if node == self.head: 
                self.head = node.next
            if node == self.tail:
                self.tail = node.prev
            if node.prev:
                node.prev.next = node.next
            if node.next:
                node.next.prev = node.prev
            # very important!
            node.prev = None
            node.next = None
            del self.hashmap[node.key]
            self.size -= 1
    

Log in to reply
 

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