432.md

432. All O`one Data Structure

Solution 1

"""
class Node:
    def __init__(self, key="", count=0):
        self.prev = None
        self.next = None
        self.keys = {key}
        self.count = count

class AllOne(object):

    def __init__(self):
        self.root = Node()
        self.root.next = self.root
        self.root.prev = self.root
        self.nodes = {}

    def inc(self, key):
        """
        :type key: str
        :rtype: None
        """
        if key not in self.nodes:
            if self.root.next is self.root or self.root.next.count > 1:
                new_node = Node(key, 1)
                new_node.prev = self.root
                new_node.next = self.root.next
                new_node.prev.next = new_node
                new_node.next.prev = new_node
                self.nodes[key] = new_node
            else:
                self.root.next.keys.add(key)
                self.nodes[key] = self.root.next
        else:
            cur_node = self.nodes[key]
            next_node = cur_node.next
            if next_node is self.root or next_node.count > cur_node.count + 1:
                new_node = Node(key, cur_node.count + 1)
                new_node.prev = cur_node
                new_node.next = cur_node.next
                new_node.prev.next = new_node
                new_node.next.prev = new_node
                self.nodes[key] = new_node
            else:
                next_node.keys.add(key)
                self.nodes[key] = next_node
            cur_node.keys.remove(key)
            if len(cur_node.keys) == 0:
                cur_node.prev.next = cur_node.next
                cur_node.next.prev = cur_node.prev

    def dec(self, key):
        """
        :type key: str
        :rtype: None
        """
        cur_node = self.nodes[key]
        if cur_node.count == 1:
            del self.nodes[key]
        else:
            prev_node = cur_node.prev
            if prev_node is self.root or prev_node.count < cur_node.count - 1:
                new_node = Node(key, cur_node.count - 1)
                new_node.prev = prev_node
                new_node.next = prev_node.next
                new_node.prev.next = new_node
                new_node.next.prev = new_node
                self.nodes[key] = new_node
            else:
                prev_node.keys.add(key)
                self.nodes[key] = prev_node
        cur_node.keys.remove(key)
        if len(cur_node.keys) == 0:
            cur_node.prev.next = cur_node.next
            cur_node.next.prev = cur_node.prev


    def getMaxKey(self):
        """
        :rtype: str
        """
        if self.root.prev is not self.root:
            return next(iter(self.root.prev.keys))
        return ""

    def getMinKey(self):
        """
        :rtype: str
        """
        if self.root.next is not self.root:
            return next(iter(self.root.next.keys))
        return ""


# Your AllOne object will be instantiated and called as such:
# obj = AllOne()
# obj.inc(key)
# obj.dec(key)
# param_3 = obj.getMaxKey()
# param_4 = obj.getMinKey()