concise python version


  • 0
    X

    class Node:
    slots = 'val', 'keys', 'prev', 'next'
    def init(self, val):
    self.val = val
    self.keys = set()

    def delnode( deltgt ):
    prev, nxt = deltgt.prev, deltgt.next
    prev.next, nxt.prev = nxt, prev
    deltgt.next = deltgt.prev = None
    return prev

    def insertafter( prev, new ):
    nxt = prev.next
    new.prev, new.next = prev, nxt
    nxt.prev = prev.next = new

    class AllOne(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        head = Node(0)
        head.prev = head.next = head
        self.__hd = head
        self.__k2n = {}
        
    def inc(self, key):
        """
        Inserts a new key <Key> with value 1. Or increments an existing key by 1.
        :type key: str
        :rtype: void
        """
        k2n = self.__k2n
        node = k2n.get(key, self.__hd)
        newval = node.val + 1
        if node is not self.__hd:
            node.keys.discard( key )
            if len( node.keys ) == 0:
                node = delnode( node )
        if node.next.val != newval:
            new = Node( newval )
            insertafter( node, new )
        node = node.next
        node.keys.add( key )
        k2n[ key ] = node
                
    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
        """
        k2n = self.__k2n
        node = k2n.get(key)
        if node is None: return 
        newval = node.val - 1
        node.keys.discard( key )
        if len( node.keys ) == 0:
            node = delnode( node )
        else:
            node = node.prev
        if newval == 0: 
            del k2n[key]
            return
        if node.val != newval:
            new = Node( newval )
            insertafter( node, new )
            node = new
        node.keys.add( key )
        k2n[key] = node
    
    def getMaxKey(self):
        """
        Returns one of the keys with maximal value.
        :rtype: str
        """
        return next(iter(self.__hd.prev.keys), '')
        
    def getMinKey(self):
        """
        Returns one of the keys with Minimal value.
        :rtype: str
        """
        return next(iter(self.__hd.next.keys), '')

Log in to reply
 

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