Python solution that beats 95.24% submissions


  • 0
    K

    The key is to swap value of nodes, not nodes themselves.

    class AllOne(object):

    """Idea:
    Use a hash k->node and a linked list node(k, cnt)
    to inc a missing, simply prepent to head and hupdate hash
    to inc a existed, +1 to cnt and advance node until the next is None or >= cnt
    similar to dec
    get max return tail
    get min return head
    """
    
    class Node(object):
        def __init__(self, k, c):
            self.key = k
            self.cnt = c
            self.next = None
            self.prev = None
    
            
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.head = self.tail = None
        self.map = dict()  # k -> node
        
    
    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.map:
            node = self.Node(key, 1)
            self.map[key] = node
            if not self.head:
                self.head = self.tail = node
            else:
                node.next = self.head
                self.head.prev = node
                self.head = node                
        else:
            node = self.map[key]
            node.cnt += 1
            while node.next and node.next.cnt < node.cnt:
                swap_key = node.next.key
                node.key, node.next.key = node.next.key, node.key
                node.cnt, node.next.cnt = node.next.cnt, node.cnt
                self.map[key] = node.next
                self.map[swap_key] = node
                node = node.next
                
    
    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.map:
            return 
        node = self.map[key]
        node.cnt -= 1
        if node.cnt == 0:
            del self.map[key]
            if self.head == self.tail == node:
                self.head = self.tail = None
            elif self.head == node:
                self.head = node.next
                node.next.prev = None
            elif self.tail == node:
                self.tail = node.prev
                node.prev.next = None
            else:
                node.prev.next = node.next
                node.next.prev = node.prev
        else:
            while node.prev and node.prev.cnt > node.cnt:
                swap_key = node.prev.key
                node.prev.key, node.key = node.key, node.prev.key
                node.prev.cnt, node.cnt = node.cnt, node.prev.cnt
                node = node.prev
                self.map[key] = node
                self.map[swap_key] = node.next
        
    
    def getMaxKey(self):
        """
        Returns one of the keys with maximal value.
        :rtype: str
        """
        if self.tail:
            return self.tail.key
        else:
            return ""
        
    
    def getMinKey(self):
        """
        Returns one of the keys with Minimal value.
        :rtype: str
        """
        if self.head:
            return self.head.key
        else:
            return ""

Log in to reply
 

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