宫水三叶的刷题日记
2023/05/05阅读：28主题：全栈蓝
【月度刷题计划同款】常见数据结构运用
题目描述
这是 LeetCode 上的 「432. 全 O(1) 的数据结构」 ，难度为 「困难」。
Tag : 「双向链表」、「哈希表」
请你设计一个用于存储字符串计数的数据结构，并能够返回计数最小和最大的字符串。
实现 AllOne 类：
-
AllOne()初始化数据结构的对象。 -
inc(String key)字符串key的计数增加 。如果数据结构中尚不存在key，那么插入计数为 的key。 -
dec(String key)字符串key的计数减少 。如果key的计数在减少后为 ，那么需要将这个key从数据结构中删除。测试用例保证：在减少计数前，key存在于数据结构中。 -
getMaxKey()返回任意一个计数最大的字符串。如果没有元素存在，返回一个空字符串""。 -
getMinKey()返回任意一个计数最小的字符串。如果没有元素存在，返回一个空字符串""。
示例：
输入
["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"
提示：
-
-
key由小写英文字母组成 -
测试用例保证：在每次调用 dec时，数据结构中总存在key -
最多调用 inc、dec、getMaxKey和getMinKey方法 次
双向链表 + 哈希表
题目要求我们支持 的查询和修改，其中查询只需返回任意一个计数次数「最多」和「最少」的元素即可（如果有）。
虽然插入的字符串长度不超过 （该数据范围的含义为字符串的哈希计算消耗可看作常数），但单纯的使用「哈希表」仅能做到 的计数，无法做到 查询。
我们可以采取和 实现一个 LRUCache & 实现一个 LFUCache 类似的思路，通过自定义节点并手写双链表来实现。
定义一个节点类 Node，除了包含用于实现双向链表的 left 和 right 以外，还包含一个数值类型的变量 cnt， 用于记录该节点存储的是计数次数为多少的元素，以及一个 Set 类型的容器，用于支持
插入和删除元素，记作 set。
同时为了快速知道某个字符串属于哪个 Node，我们还需要开一个「哈希表」进行定位（以字符串为哈希表的键，字符串所在 Node 作为值），当定位到字符串对应的 Node 之后则可以利用双向链表的
增加/修改/删除。
在双向链表中，起始只有两个哨兵节点 hh 和 tt ，当进行若干 inc/dec 操作后的基本形态为：
对应几个操作：
inc/dec 操作：当对一个字符串 key 进行「增加计数」或「减少计数」时，先在哈希表中看 key 是否存在：
-
若存在：根据其所属的 Node的计数cnt为多少，并结合当前是「增加计数」还是「减少计数」来决定是找Node的「右节点」还是「左节点」，同时检查相邻节点的计数值cnt是否为目标值，对应要检查数值是 和 ：-
若相邻节点的 cnt为目标值：即目标节点存在，将key从原Node的set集合中移除，并添加到目标节点的集合中，更新哈希表； -
若相邻节点的 cnt不是目标值：则需要创建相应的目标节点，并构建双向链表关系，把key存入新创建的目标节点，更新哈希表。
-
-
若不存在（只能是 inc操作）：查找是否存在 的节点（也就是检查hh.right节点的计数值）：-
如果存在 的目标节点：将 key添加到目标节点的set集合中，更新哈希表； -
若不存在 的目标节点：创建相应的节点，并构建双向关系，并构建双向链表关系，把 key存入新创建的目标节点，更新哈希表。
-
getMaxKey/getMinKey 操作：分别从 tt.left 和 hh.right 中尝试查找，如果存在非哨兵节点，则从节点的 set 集合中取任意元素进行返回，否则返回空串。
最后，为了确保 getMaxKey/getMinKey 操作能够严格
，我们在进行 inc/dec 操作时我们需要对一些 set 容量为
的节点进行释放，即解除其所在双向链表的关系。
代码：
class AllOne {
class Node {
int cnt;
Set<String> set = new HashSet<>();
Node left, right;
Node(int _cnt) {
cnt = _cnt;
}
}
Node hh, tt;
Map<String, Node> map = new HashMap<>();
public AllOne() {
hh = new Node(-1000); tt = new Node(-1000);
hh.right = tt; tt.left = hh;
}
void clear(Node node) {
if (node.set.size() == 0) {
node.left.right = node.right;
node.right.left = node.left;
}
}
public void inc(String key) {
if (map.containsKey(key)) {
Node node = map.get(key);
node.set.remove(key);
int cnt = node.cnt;
Node next = null;
if (node.right.cnt == cnt + 1) {
next = node.right;
} else {
next = new Node(cnt + 1);
next.right = node.right;
next.left = node;
node.right.left = next;
node.right = next;
}
next.set.add(key);
map.put(key, next);
clear(node);
} else {
Node node = null;
if (hh.right.cnt == 1) {
node = hh.right;
} else {
node = new Node(1);
node.right = hh.right;
node.left = hh;
hh.right.left = node;
hh.right = node;
}
node.set.add(key);
map.put(key, node);
}
}
public void dec(String key) {
Node node = map.get(key);
node.set.remove(key);
int cnt = node.cnt;
if (cnt == 1) {
map.remove(key);
} else {
Node prev = null;
if (node.left.cnt == cnt - 1) {
prev = node.left;
} else {
prev = new Node(cnt - 1);
prev.right = node;
prev.left = node.left;
node.left.right = prev;
node.left = prev;
}
prev.set.add(key);
map.put(key, prev);
}
clear(node);
}
public String getMaxKey() {
Node node = tt.left;
for (String str : node.set) return str;
return "";
}
public String getMinKey() {
Node node = hh.right;
for (String str : node.set) return str;
return "";
}
}
-
时间复杂度： -
空间复杂度：
最后
这是我们「刷穿 LeetCode」系列文章的第 No.432 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉
作者介绍