题目描述
这是 LeetCode 上的 432. 全 O(1) 的数据结构 ，难度为 困难。
Tag : 「双向链表」、「哈希表」
请你设计一个用于存储字符串计数的数据结构，并能够返回计数最小和最大的字符串。
实现 AllOne 类：
AllOne()初始化数据结构的对象。inc(String key)字符串key的计数增加 11 。如果数据结构中尚不存在key，那么插入计数为 11 的key。dec(String key)字符串key的计数减少 11 。如果key的计数在减少后为 00 ，那么需要将这个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" 复制代码
提示：
- 1 <= key.length <= 101<=key.length<=10
key由小写英文字母组成- 测试用例保证：在每次调用
dec时，数据结构中总存在key - 最多调用
inc、dec、getMaxKey和getMinKey方法 5 * 10^45∗104 次
双向链表 + 哈希表
题目要求我们支持 O(1)O(1) 的查询和修改，其中查询只需返回任意一个计数次数「最多」和「最少」的元素即可（如果有）。
虽然插入的字符串长度不超过 1010（该数据范围的含义为字符串的哈希计算消耗可看作常数），但单纯的使用「哈希表」仅能做到 O(1)O(1) 的计数，无法做到 O(1)O(1) 查询。
我们可以采取和 实现一个 LRUCache & 实现一个 LFUCache 类似的思路，通过自定义节点并手写双链表来实现。
定义一个节点类 Node，除了包含用于实现双向链表的 left 和 right 以外，还包含一个数值类型的变量 val， 用于记录该节点存储的是计数次数为多少的元素，以及一个 Set 类型的容器，用于支持 O(1)O(1) 插入和删除元素，记作 set。
同时为了快速知道某个字符串属于哪个 Node，我们还需要开一个「哈希表」进行定位（以字符串为哈希表的键，字符串所在 Node 作为值），当定位到字符串对应的 Node 之后则可以利用「双向链表」的 O(1)O(1) 增加/修改/删除。
在双向链表中，起始只有两个哨兵节点 hh 和 tt ，当进行若干 inc/dec 操作后的基本形态为：
对应几个操作：
inc/dec 操作：当对一个字符串 key 进行「增加计数」或「减少计数」时，先在哈希表中看 key 是否存在：
- 若存在：根据其所属的
Node的计数cnt为多少，并结合当前是「增加计数」还是「减少计数」来决定是找Node的「右节点」还是「左节点」，同时检查相邻节点的计数值cnt是否为目标值，对应要检查数值是cnt + 1cnt+1和cnt - 1cnt−1：
- 若相邻节点的
cnt为目标值：即目标节点存在，将key从原Node的set集合中移除，并添加到目标节点的集合中，更新哈希表； - 若相邻节点的
cnt不是目标值：则需要创建相应的目标节点，并构建双向链表关系，把key存入新创建的目标节点，更新哈希表。
- 若不存在（只能是
inc操作）：查找是否存在cnt = 1cnt=1的节点（也就是检查hh.right节点的计数值）：
- 如果存在 cnt = 1cnt=1 的目标节点：将
key添加到目标节点的set集合中，更新哈希表； - 若不存在 cnt = 1cnt=1 的目标节点：创建相应的节点，并构建双向关系，并构建双向链表关系，把
key存入新创建的目标节点，更新哈希表。
getMaxKey/getMinKey 操作：分别从 tt.left 和 hh.right 中尝试查找，如果存在非哨兵节点，则从节点的 set 集合中取任意元素进行返回，否则返回空串。
最后，为了确保 getMaxKey/getMinKey 操作能够严格 O(1)O(1)，我们在进行 inc/dec 操作时我们需要对一些 set 容量为 00 的节点进行释放，即解除其所在双向链表的关系。
代码：
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 ""; } } 复制代码
- 时间复杂度：O(1)O(1)
- 空间复杂度：O(n)O(n)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.432 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
