LeetCode 题解工作台
全 O(1) 的数据结构
请你设计一个用于存储字符串计数的数据结构，并能够返回计数最小和最大的字符串。 实现 AllOne 类： AllOne() 初始化数据结构的对象。 inc(String key) 字符串 key 的计数增加 1 。如果数据结构中尚不存在 key ，那么插入计数为 1 的 key 。 dec(Strin…
4
题型
2
代码语言
3
相关题
当前训练重点
困难 · 链表指针操作
答案摘要
class Node: def __init__(self, key='', cnt=0):
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 链表指针操作 题型思路
题目描述
请你设计一个用于存储字符串计数的数据结构，并能够返回计数最小和最大的字符串。
实现 AllOne 类：
AllOne()初始化数据结构的对象。inc(String key)字符串key的计数增加1。如果数据结构中尚不存在key，那么插入计数为1的key。dec(String key)字符串key的计数减少1。如果key的计数在减少后为0，那么需要将这个key从数据结构中删除。测试用例保证：在减少计数前，key存在于数据结构中。getMaxKey()返回任意一个计数最大的字符串。如果没有元素存在，返回一个空字符串""。getMinKey()返回任意一个计数最小的字符串。如果没有元素存在，返回一个空字符串""。
注意：每个函数都应当满足 O(1) 平均时间复杂度。
示例：
输入
["AllOne", "inc", "inc", "getMaxKey", "getMinKey", "inc", "getMaxKey", "getMinKey"]
[[], ["hello"], ["hello"], [], [], ["leet"], [], []]
输出
[null, null, null, "hello", "hello", null, "hello", "leet"]
解释
AllOne allOne = new AllOne();
allOne.inc("hello");
allOne.inc("hello");
allOne.getMaxKey(); // 返回 "hello"
allOne.getMinKey(); // 返回 "hello"
allOne.inc("leet");
allOne.getMaxKey(); // 返回 "hello"
allOne.getMinKey(); // 返回 "leet"
提示：
1 <= key.length <= 10key由小写英文字母组成- 测试用例保证：在每次调用
dec时，数据结构中总存在key - 最多调用
inc、dec、getMaxKey和getMinKey方法5 * 104次
解题思路
方法一
class Node:
def __init__(self, key='', cnt=0):
self.prev = None
self.next = None
self.cnt = cnt
self.keys = {key}
def insert(self, node):
node.prev = self
node.next = self.next
node.prev.next = node
node.next.prev = node
return node
def remove(self):
self.prev.next = self.next
self.next.prev = self.prev
class AllOne:
def __init__(self):
self.root = Node()
self.root.next = self.root
self.root.prev = self.root
self.nodes = {}
def inc(self, key: str) -> None:
root, nodes = self.root, self.nodes
if key not in nodes:
if root.next == root or root.next.cnt > 1:
nodes[key] = root.insert(Node(key, 1))
else:
root.next.keys.add(key)
nodes[key] = root.next
else:
curr = nodes[key]
next = curr.next
if next == root or next.cnt > curr.cnt + 1:
nodes[key] = curr.insert(Node(key, curr.cnt + 1))
else:
next.keys.add(key)
nodes[key] = next
curr.keys.discard(key)
if not curr.keys:
curr.remove()
def dec(self, key: str) -> None:
root, nodes = self.root, self.nodes
curr = nodes[key]
if curr.cnt == 1:
nodes.pop(key)
else:
prev = curr.prev
if prev == root or prev.cnt < curr.cnt - 1:
nodes[key] = prev.insert(Node(key, curr.cnt - 1))
else:
prev.keys.add(key)
nodes[key] = prev
curr.keys.discard(key)
if not curr.keys:
curr.remove()
def getMaxKey(self) -> str:
return next(iter(self.root.prev.keys))
def getMinKey(self) -> str:
return next(iter(self.root.next.keys))
# 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()
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(1) |
| 空间 | O(N) |
面试官常问的追问
外企场景- question_mark
Check if candidate correctly uses both hash map and doubly-linked list to maintain O(1) operations.
- question_mark
Observe if pointer updates are handled safely when incrementing or decrementing keys.
- question_mark
Look for understanding of how frequency nodes are linked and how keys move between them.
常见陷阱
外企场景- error
Updating the doubly-linked list incorrectly when moving keys between frequency nodes, causing incorrect max/min keys.
- error
Failing to remove empty frequency nodes after a key decrement, which can break O(1) assumptions.
- error
Using linear scans instead of pointer manipulation, leading to performance degradation.
进阶变体
外企场景- arrow_right_alt
Implement a version that also supports returning all keys with a given count in O(1) time.
- arrow_right_alt
Modify the data structure to allow bulk increment or decrement of multiple keys efficiently.
- arrow_right_alt
Design a version that maintains counts for integer keys instead of strings while keeping O(1) operations.