my just so so python solution


  • 0
    B
    class Node:
        def __init__(self, val):
            self.val = val
            self.keys = set()
            self.prev = self.next = None
        
        def addPrev(self, node):
            p, n = self.prev, self
            p.next, node.prev, node.next, n.prev = node, p, n, node
        
        def addNext(self, node):
            p, n = self, self.next
            p.next, node.prev, node.next, n.prev = node, p, n, node
        
        def remove(self):
            p, n = self.prev, self.next
            p.next, n.prev = n, p
    
    class AllOne:
        
        def __init__(self):
            """
            Initialize your data structure here.
            """
            self._m = {}
            self._h, self._t = Node(0), Node(sys.maxsize)
            self._h.next, self._t.pref = self._t, self._h
    
        def inc(self, key):
            """
            Inserts a new key <Key> with value 1. Or increments an existing key by 1.
            :type key: str
            :rtype: void
            """
            if key not in self._m:
                first = self._h.next
                if first.val != 1:
                    first = Node(1)
                    self._h.addNext(first)
                first.keys.add(key)
                self._m[key] = first
            else:
                node = self._m[key]
                n = node.next
                if node.val + 1 != n.val:
                    n = Node(node.val + 1)
                    node.addNext(n)
                n.keys.add(key)
                node.keys.remove(key)
                if not node.keys: node.remove()
                self._m[key] = n
    
        def dec(self, key):
            """
            Decrements an existing key by 1. If Key's value is 1, remove it from the data structure.
            :type key: str
            :rtype: void
            """
            if key not in self._m: return
            node = self._m[key]
            if node.val == 1: del self._m[key]
            else:
                p = node.prev
                if node.val - 1 != p.val:
                    p = Node(node.val - 1)
                    node.addPrev(p)
                p.keys.add(key)
                self._m[key] = p
            node.keys.remove(key)
            if not node.keys: node.remove()
    
        def getMaxKey(self):
            """
            Returns one of the keys with maximal value.
            :rtype: str
            """
            if not self._m: return ''
            for key in self._t.prev.keys: return key
    
        def getMinKey(self):
            """
            Returns one of the keys with Minimal value.
            :rtype: str
            """
            if not self._m: return ''
            for key in self._h.next.keys: return key
    

Log in to reply
 

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