LeetCode 432 All O one Data Structure

LeetCode

<div>

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:

<pre>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" </pre>

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 to inc, dec, getMaxKey, and getMinKey.

</div>

题目大意：

设计数据结构，使其支持增加或减少一个单词的频数，最大或最小单词的频数。注意最小频数不能为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)