LeetCode 432 All O one Data Structure

LeetCode

Design a data structure to store the strings’ count with the ability to return the strings with minimum and maximum counts.

Implement the AllOne class:

AllOne() Initializes the object of the data structure. inc(String key) Increments the count of the string key by 1. If key does not exist in the data structure, insert it with count 1.
dec(String key) Decrements the count of the string key by 1. If the count of key is 0 after the decrement, remove it from the data structure. It is guaranteed that key exists in the data structure before the decrement. getMaxKey() Returns one of the keys with the maximal count. If no element exists, return an empty string "".
getMinKey() Returns one of the keys with the minimum count. If no element exists, return an empty string "".

Example 1:

Input
[“AllOne”, “inc”, “inc”, “getMaxKey”, “getMinKey”, “inc”, “getMaxKey”, “getMinKey”]
[[], [“hello”], [“hello”], [], [], [“leet”], [], []]
Output
[null, null, null, “hello”, “hello”, null, “hello”, “leet”]

Explanation
AllOne allOne = new AllOne();
allOne.inc(“hello”);
allOne.inc(“hello”);
allOne.getMaxKey(); // return “hello”
allOne.getMinKey(); // return “hello”
allOne.inc(“leet”);
allOne.getMaxKey(); // return “hello”
allOne.getMinKey(); // return “leet”

Constraints: 1 <= key.length <= 10
key consists of lowercase English letters. It is guaranteed that for each call to dec, key is existing in the data structure.
At most `5 10<sup>4</sup>calls will be made toinc,dec,getMaxKey, andgetMinKey`.

题目大意：

设计数据结构，使其支持增加或减少一个单词的频数，最大或最小单词的频数。注意最小频数不能为0

解题思路：

这个频数有点似LRU的分层思路，加入self.max_freq, 其他操作都可以实现，但是dec操作不能达到O(1), 因为若某个最小频数单词从1变成0，需要检索频率到下一个有节点的层。
改进就是要将频率的的值连起来，所以参考LRU，map的key是频率，value是node，node中含有freq，形成一个环。而node含有该频率对应的单词set，inc/dec就是将单词移动另一个node中

解题步骤：

N/A

注意事项：

1. 与LRU区别: map的key是频率，node含有频率和单词set，数据结构加入key_to_count。LL是从最大频率到最小频率
2. inc操作将节点从原频率node移到下一个频率node，若新node不存在，调用append_before. 然后从原频率node的单词set中删除该单词，若set为空，删除此node以及map中的entry
3. dec与inc类似，但要注意频率变成0的情况：不移到新的node，且从key_to_count中删除该单词

Python代码：

class AllOne(TestCases):

    def __init__(self):
        self.freq_to_node = {}
        self.head = ListNode(0)
        self.tail = ListNode(0)
        self.head.next, self.tail.prev = self.tail, self.head
        self.key_to_count = collections.defaultdict(int)

    def inc(self, key: str) -> None:
        count = self.key_to_count[key]
        old_node = self.freq_to_node[count] if count in self.freq_to_node else self.tail
        count += 1
        if count not in self.freq_to_node:
            self.freq_to_node[count] = self.append_before(old_node)
        new_node = self.freq_to_node[count]
        new_node.key_set.add(key)
        self.key_to_count[key] = count

        count -= 1
        if count in self.freq_to_node and key in self.freq_to_node[count].key_set:
            self.freq_to_node[count].key_set.remove(key)
            if len(self.freq_to_node[count].key_set) == 0:
                self.remove_node(self.freq_to_node[count])
                self.freq_to_node.pop(count) # remember

    def dec(self, key: str) -> None:
        count = self.key_to_count[key]
        old_node = self.freq_to_node[count] if count in self.freq_to_node else self.head
        count -= 1
        if count > 0: # remember
            if count not in self.freq_to_node:
                self.freq_to_node[count] = self.append_after(old_node)
            new_node = self.freq_to_node[count]
            new_node.key_set.add(key)
            self.key_to_count[key] = count
        else:
            self.key_to_count.pop(key)

        count += 1
        if count in self.freq_to_node and key in self.freq_to_node[count].key_set:
            self.freq_to_node[count].key_set.remove(key)
            if len(self.freq_to_node[count].key_set) == 0:
                self.remove_node(self.freq_to_node[count])
                self.freq_to_node.pop(count)

    def getMaxKey(self) -> str:
        node = self.head.next
        return '' if node == self.tail else next(iter(node.key_set))

    def getMinKey(self) -> str:
        node = self.tail.prev
        return '' if node == self.head else next(iter(node.key_set))

    def append_before(self, node):
        new_node = ListNode(node.freq + 1)
        predecessor, successor = node.prev, node
        predecessor.next, new_node.prev = new_node, predecessor
        new_node.next, successor.prev = successor, new_node
        return new_node

    def append_after(self, node):
        new_node = ListNode(node.freq - 1)
        predecessor, successor = node, node.next
        predecessor.next, new_node.prev = new_node, predecessor
        new_node.next, successor.prev = successor, new_node
        return new_node

    def remove_node(self, node):
        predecessor, successor = node.prev, node.next
        predecessor.next, successor.prev = successor, predecessor
        node.prev, node.next = None, None


class ListNode:
    def __init__(self, freq=0, next=None, prev=None):
        self.key_set = set()
        self.freq = freq
        self.next = next
        self.prev = prev

算法分析：

时间复杂度为O(1)，空间复杂度O(n)