这个题解使用双向链表和哈希表来实现AllOne类的功能。链表中的每个节点包含一个计数值和一个存储对应计数值的键的集合。哈希表用于快速查找每个键所在的链表节点。在inc和dec操作中，通过更新链表节点的键集合和在链表中插入或删除节点来维护计数值的有序性。getMaxKey和getMinKey操作可以通过返回链表头尾节点的任意一个键来实现。
时间复杂度: O(1)
空间复杂度: O(n)
class DListNode:
def __init__(self, val):
self.val = val # 节点的计数值
self.keys = set() # 存储计数值为val的键的集合
self.next = None # 指向链表的下一个节点
self.prev = None # 指向链表的前一个节点
def __repr__(self):
keys = list(self.keys)
return "'" + str(self.val) + " " + ",".join(keys) + "'"
class AllOne:
def __init__(self):
"""
Initialize your data structure here.
"""
self._table = dict() # 哈希表，用于快速查找键所在的链表节点
self._head = DListNode(0) # 双向链表的头节点，哨兵节点
self._tail = DListNode(0) # 双向链表的尾节点，哨兵节点
self._head.next = self._tail
self._tail.prev = self._head
def _first_node(self):
return self._head.next # 返回链表的第一个节点（除哨兵节点外）
def _last_node(self):
return self._tail.prev # 返回链表的最后一个节点（除哨兵节点外）
def _insert_front(self, node):
# 在链表头部插入节点
node.next = self._head.next
node.prev = self._head
self._head.next.prev = node
self._head.next = node
def _insert_last(self, node):
# 在链表尾部插入节点
node.next = self._tail
node.prev = self._tail.prev
self._tail.prev.next = node
self._tail.prev = node
def _delete_node(self, node):
# 从链表中删除节点
node.prev.next = node.next
node.next.prev = node.prev
def inc(self, key: str) -> None:
"""
Inserts a new key <Key> with value 1. Or increments an existing key by 1.
"""
if key not in self._table:
# 如果key不在哈希表中
first_node = self._first_node()
if first_node.val != 1 or first_node == self._tail:
# 如果第一个节点的计数值不为1或链表为空，创建新节点并插入链表头部
new_node = DListNode(1)
new_node.keys.add(key)
self._insert_front(new_node)
self._table[key] = new_node
else:
# 否则，将key添加到第一个节点的键集合中
self._table[key] = first_node
first_node.keys.add(key)
else:
# 如果key在哈希表中
prev_node = self._table[key]
prev_val = prev_node.val
if prev_node.next == self._tail or prev_node.next.val != prev_val + 1:
# 如果当前节点是最后一个节点或下一个节点的计数值不等于当前计数值+1，创建新节点并插入当前节点之后
new_node = DListNode(prev_val + 1)
new_node.keys.add(key)
new_node.next = prev_node.next
new_node.prev = prev_node
prev_node.next.prev = new_node
prev_node.next = new_node
# 更新哈希表
self._table[key] = new_node
# 更新当前节点
prev_node.keys.discard(key)
if len(prev_node.keys) == 0:
self._delete_node(prev_node)
else:
# 否则，将key添加到下一个节点的键集合中
self._table[key] = prev_node.next
prev_node.next.keys.add(key)
prev_node.keys.discard(key)
if len(prev_node.keys) == 0:
self._delete_node(prev_node)
def dec(self, key: str) -> None:
"""
Decrements an existing key by 1. If Key's value is 1, remove it from the data structure.
"""
if key not in self._table:
return
prev_node = self._table[key]
prev_val = prev_node.val
if prev_val == 1:
# 如果当前计数值为1，从哈希表和链表中删除key
del self._table[key]
prev_node.keys.discard(key)
if len(prev_node.keys) == 0:
self._delete_node(prev_node)
else:
if prev_node.prev == self._head or prev_node.prev.val != prev_val - 1:
# 如果当前节点是第一个节点或前一个节点的计数值不等于当前计数值-1，创建新节点并插入当前节点之前
new_node = DListNode(prev_val - 1)
new_node.keys.add(key)
new_node.next = prev_node
new_node.prev = prev_node.prev
prev_node.prev.next = new_node
prev_node.prev = new_node
self._table[key] = new_node
prev_node.keys.discard(key)
if len(prev_node.keys) == 0:
self._delete_node(prev_node)
else:
# 否则，将key添加到前一个节点的键集合中
self._table[key] = prev_node.prev
prev_node.prev.keys.add(key)
prev_node.keys.discard(key)
if len(prev_node.keys) == 0:
self._delete_node(prev_node)
def getMaxKey(self) -> str:
"""
Returns one of the keys with maximal value.
"""
node = self._tail.prev
if node == self._head:
return "" # 如果链表为空，返回空字符串
keys = node.keys
return next(iter(keys)) # 返回最后一个节点的任意一个键
def getMinKey(self) -> str:
"""
Returns one of the keys with Minimal value.
"""
node = self._head.next
if node == self._tail:
return "" # 如果链表为空，返回空字符串
keys = node.keys
return next(iter(keys)) # 返回第一个节点的任意一个键