Python all O(1) 99ms solution using Sorted LinkedList and HashMap


  • 0
    X
    class AllOne(object):
    
        # SHDLL (Super Handy Doubly Linked List)
        class LinkedNode(object):
            def __init__(self,prev,next,key,val):
                self.prev = prev
                self.next = next
                self.key = key
                self.val = val
            def insertBefore(self,node):
                # insert given node in front of self
                self.prev.next = node
                node.prev = self.prev
                node.next = self
                self.prev = node
        
        def __init__(self):
            self.HEAD = self.LinkedNode(None,None,'',None)
            self.TAIL = self.LinkedNode(self.HEAD,None,'',None)
            self.HEAD.next = self.TAIL
            self.nodes = {}
            self.levels = {1:self.TAIL,-1:self.TAIL}
    
        def deleteNode(self,node):
            # take given node out of LinkedList
            # invariant: given node.val should appear to be correct
            node.prev.next = node.next
            node.next.prev = node.prev
            if self.levels[node.val] == node:
                self.levels[node.val] = node.next
                
        def insertNode(self,node):
            # insert given node into LinkedList
            # invariant: MIN( all the level pointer that points to self.levels[insertPoint] ) = node.val
            insertPoint = node.val if node.val in self.levels else -1
            self.levels[insertPoint].insertBefore(node)
            self.levels[node.val] = node
        
        def inc(self, key):
            if key in self.nodes:
                node = self.nodes[key]
                if node.next.val > node.val or node.next == self.TAIL:
                    # appear to be in right place
                    node.val += 1
                    self.levels[node.val]=node
                    
                elif node.next.val == node.val:
                    self.deleteNode(node)
                    node.val += 1
                    self.insertNode(node)
            else: # new item
                node = self.LinkedNode(None,None,key,1)
                self.nodes[key] = node
                self.insertNode(node)
    
    
        def dec(self, key):
            if key not in self.nodes:
                return
            node = self.nodes[key]
            
            if node.val == 1:
                self.deleteNode(node)
                del self.nodes[key]
                return 
                
            if self.levels[node.val-1]!=node:
                self.deleteNode(node)
                self.levels[node.val-1].insertBefore(node)
            else:
                self.levels[node.val]=node.next
            
            node.val -= 1
            self.levels[node.val] = node
    
        def getMaxKey(self):
            return self.TAIL.prev.key
    
        def getMinKey(self):
            return self.HEAD.next.key
    
    

  • 0
    L

    @xueguang Your solution only passes because of a small amount of test cases.
    ["AllOne","inc","inc","inc","inc","inc","inc","getMinKey","dec","dec","getMaxKey"]
    [[],["c"],["c"],["b"],["b"],["b"],["a"],[],["b"],["b"],[]]


Log in to reply
 

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