本文最后更新于238 天前，其中的信息可能已经过时，如有错误请发送邮件到2446865563@qq.com
1.题目基本信息
1.1.题目描述
请你设计一个用于存储字符串计数的数据结构，并能够返回计数最小和最大的字符串。
实现 AllOne 类：
-
AllOne() 初始化数据结构的对象。
-
inc(String key) 字符串 key 的计数增加 1 。如果数据结构中尚不存在 key ，那么插入计数为 1 的 key 。
-
dec(String key) 字符串 key 的计数减少 1 。如果 key 的计数在减少后为 0 ，那么需要将这个 key 从数据结构中删除。测试用例保证：在减少计数前，key 存在于数据结构中。
-
getMaxKey() 返回任意一个计数最大的字符串。如果没有元素存在，返回一个空字符串 "" 。
-
getMinKey() 返回任意一个计数最小的字符串。如果没有元素存在，返回一个空字符串 "" 。
注意：每个函数都应当满足 O(1) 平均时间复杂度。
1.2.题目地址
https://leetcode.cn/problems/all-oone-data-structure/description/
2.解题方法
2.1.解题思路
双向链表+哈希表
2.2.解题步骤
请看“注释”
3.解题代码
python代码-方法一（O(1)）
class DNode():
def __init__(self, keys = [], freq = 1):
self.keys = set(keys) # 这里用的存储（无需顺序）
self.freq = freq
self.prev = None
self.next = None
class AllOne:
# 思路：双向链表+哈希表（O(1)）
def __init__(self):
self.root = self.createNewList()
self.cache = {}
# TOOL：创建新链表
def createNewList(self):
dumbNode = DNode([], 0)
dumbNode.next = dumbNode
dumbNode.prev = dumbNode
return dumbNode
# TOOL：判断链表是否为空
def empty(self, node):
return node.next == node
# TOOL：在prevNode后面插入node节点
def insertNode(self, prevNode, node):
node.next = prevNode.next
node.next.prev = node
node.prev = prevNode
prevNode.next = node
# TOOL：删除节点node
def deleteNode(self, node):
node.next.prev = node.prev
node.prev.next = node.next
def inc(self, key: str) -> None:
if key in self.cache:
# 第一步，key在cache中时，保证下一个node.freq+1频率的节点存在；移除node中的key，如果移除后keys长度为0，则将结点一起删除；将key插入node.freq+1频率的节点中，并更新cache
node = self.cache[key]
if node.next is self.root or node.next.freq > node.freq + 1:
self.insertNode(node, DNode([], node.freq + 1))
node.keys.remove(key)
if len(node.keys) == 0:
self.deleteNode(node)
node.next.keys.add(key)
self.cache[key] = node.next
else:
# 第二步，key不在cache中，保证频率为1的节点存在；然后插入其中并更新cache
if self.root.next is self.root or self.root.next.freq != 1:
self.insertNode(self.root, DNode([], freq = 1))
self.root.next.keys.add(key)
self.cache[key] = self.root.next
def dec(self, key: str) -> None:
# 第一步，如果key不在cache中，直接返回
if key not in self.cache:
return
# 第二步，如果key在cache中；如果node的频数为1，则直接从node.keys中删除并更新cache，如果移除后keys长度为0，则将结点一起删除，并更新cache。如果node的频数大于1，则保证node.freq-1频数的节点存在；再将key插入node.prev节点中，并更新cache；然后从node.keys中移除key，如果移除key后节点的keys为空，则连带节点一起删除
node = self.cache[key]
if node.freq == 1:
node.keys.remove(key)
if len(node.keys) == 0:
self.deleteNode(node)
del self.cache[key] # 并从cache中删除
else:
if node.prev is self.root or node.prev.freq != node.freq - 1:
self.insertNode(node.prev, DNode([], node.freq - 1))
node.prev.keys.add(key)
self.cache[key] = node.prev
node.keys.remove(key)
if len(node.keys) == 0:
self.deleteNode(node)
def getMaxKey(self) -> str:
return next(iter(self.root.prev.keys)) if self.root.next is not self.root else ""
def getMinKey(self) -> str:
return next(iter(self.root.next.keys)) if self.root.next is not self.root else ""python代码-方法二（O(length(freqMap))）
class DNode2():
def __init__(self, key = 0):
self.key = key
self.freq = 1
self.prev = None
self.next = None
class AllOne1:
# 思路：双向链表+哈希表（O(len(freqMap))）
def __init__(self):
self.cache = {}
self.freqMap = {}
self.minFreq = self.maxFreq = 0
# TOOL：创建新链表
def createNewList(self):
dumbNode = DNode(0)
dumbNode.next = dumbNode
dumbNode.prev = dumbNode
return dumbNode
# TOOL：判断链表是否为空
def empty(self, node):
return node.next == node
# TOOL：在prevNode后面插入node节点
def insertNode(self, prevNode, node):
node.next = prevNode.next
node.next.prev = node
node.prev = prevNode
prevNode.next = node
# TOOL：删除节点node
def deleteNode(self, node):
node.next.prev = node.prev
node.prev.next = node.next
def inc(self, key: str) -> None:
# 第一步，保证cache中存在key节点
if key in self.cache:
node = self.cache[key]
node.freq += 1
self.deleteNode(node)
if self.empty(self.freqMap[node.freq - 1]):
del self.freqMap[node.freq - 1]
if node.freq not in self.freqMap:
self.freqMap[node.freq] = self.createNewList()
self.insertNode(self.freqMap[node.freq], node)
else:
node = DNode(key)
self.cache[key] = node
if node.freq not in self.freqMap:
self.freqMap[node.freq] = self.createNewList()
self.insertNode(self.freqMap[node.freq], node)
# 第二步，更新minFreq和maxFreq（根据是否在freqMap中进行更新）
# if self.minFreq not in self.freqMap:
# self.minFreq = node.freq
# if node.freq > self.maxFreq:
# self.maxFreq = node.freq
if self.freqMap:
self.minFreq = min(list(self.freqMap.keys()))
self.maxFreq = max(list(self.freqMap.keys()))
else:
self.minFreq = self.maxFreq = 0
def dec(self, key: str) -> None:
# 第一步，保证cache中存在key节点
if key not in self.cache:
return
node = self.cache[key]
node.freq -= 1
self.deleteNode(node)
if self.empty(self.freqMap[node.freq + 1]):
del self.freqMap[node.freq + 1]
if node.freq > 0:
if node.freq not in self.freqMap:
self.freqMap[node.freq] = self.createNewList()
self.insertNode(self.freqMap[node.freq], node)
else:
del self.cache[key]
# 第二步，更新minFreq和maxFreq（根据是否在freqMap中进行更新）
if self.freqMap:
self.minFreq = min(list(self.freqMap.keys()))
self.maxFreq = max(list(self.freqMap.keys()))
else:
self.minFreq = self.maxFreq = 0
# if not self.freqMap:
# self.minFreq = 0
# elif self.minFreq not in self.freqMap or self.empty(self.freqMap[self.minFreq]):
# self.minFreq = min(list(self.freqMap.keys()))
def getMaxKey(self) -> str:
return self.freqMap[self.maxFreq].next.key if self.maxFreq in self.freqMap else ""
def getMinKey(self) -> str:
return self.freqMap[self.minFreq].next.key if self.minFreq in self.freqMap else ""4.执行结果
