Python solution with implementing Deque


  • 1
    L
    class _Node:
        def __init__(self, key, value):
            self.key = key
            self.value = value
            self.pre = None
            self.next = None
            
    
    class _Deque:
        def __init__(self):
            self.head = _Node(None, None)
            self.tail = self.head
            self.size = 0
        
        def __len__(self):
            return self.size
        
        def pop(self):
            node = self.tail
            self.tail = self.tail.pre
            self.tail.next = None
            self.size -= 1
            return node
        
        def appendleft(self, node):
            if self.head.next:
                node.next = self.head.next
                node.pre = self.head
                self.head.next.pre = node
                self.head.next = node
            else:
                self.head.next = node
                node.pre = self.head
                self.tail = node
            self.size += 1
        
        def remove(self, node):
            if not node.next:  # node is tail
                self.tail = self.tail.pre
                self.tail.next = None
            else:
                node.next.pre = node.pre
                node.pre.next = node.next
            self.size -= 1
        
    class LRUCache:
        # @param capacity, an integer
        def __init__(self, capacity):
            self.capacity = capacity
            self.dq = _Deque()
            self.k2v = {}
            
    
        # @return an integer
        def get(self, key):
            if key not in self.k2v:
                return -1
            node = self.k2v[key]
            self.dq.remove(node)
            self.dq.appendleft(node)
            return node.value
                
                
        # @param key, an integer
        # @param value, an integer
        # @return nothing
        def set(self, key, value):
            if key not in self.k2v:
                if len(self.dq) == self.capacity:
                    old_node = self.dq.pop()
                    del self.k2v[old_node.key]
                node = _Node(key, value)
                self.dq.appendleft(node)
                self.k2v[key] = node
                    
            else:
                node = self.k2v[key]
                self.dq.remove(node)
                self.dq.appendleft(node)
                node.value = value
    

    If we use collections.deque.remove(), it's O(n). As a result, I implement a simple Deque.


Log in to reply
 

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