题目形容
这是 LeetCode 上的 432. 全 O(1) 的数据结构 ,难度为 艰难。
Tag :「双向链表」、「哈希表」
请你设计一个用于存储字符串计数的数据结构,并可能返回计数最小和最大的字符串。
实现 AllOne
类:
AllOne()
初始化数据结构的对象。inc(String key)
字符串key
的计数减少 $1$。如果数据结构中尚不存在key
,那么插入计数为 $1$ 的key
。dec(String key)
字符串key
的计数缩小 $1$。如果key
的计数在缩小后为 $0$,那么须要将这个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 <= 10$
key
由小写英文字母组成- 测试用例保障:在每次调用
dec
时,数据结构中总存在key
- 最多调用
inc
、dec
、getMaxKey
和getMinKey
办法 $5 * 10^4$ 次
双向链表 + 哈希表
题目要求咱们反对 $O(1)$ 的查问和批改,其中查问只需返回任意一个计数次数「最多」和「起码」的元素即可(如果有)。
尽管插入的字符串长度不超过 $10$(该数据范畴的含意为字符串的哈希计算耗费可看作常数),但单纯的应用「哈希表」仅能做到 $O(1)$ 的计数,无奈做到 $O(1)$ 查问。
咱们能够采取和 实现一个 LRUCache & 实现一个 LFUCache 相似的思路,通过自定义节点并手写双链表来实现。
定义一个节点类 Node
,除了蕴含用于实现双向链表的 left
和 right
以外,还蕴含一个数值类型的变量 cnt
,用于记录该节点存储的是计数次数为多少的元素,以及一个 Set
类型的容器,用于反对 $O(1)$ 插入和删除元素,记作 set
。
同时为了疾速晓得某个字符串属于哪个 Node
,咱们还须要开一个「哈希表」进行定位(以字符串为哈希表的键,字符串所在 Node
作为值),当定位到字符串对应的 Node
之后则能够利用双向链表的 $O(1)$ 减少 / 批改 / 删除。
在双向链表中,起始只有两个哨兵节点 hh
和 tt
,当进行若干 inc/dec
操作后的根本状态为:
对应几个操作:
inc/dec
操作:当对一个字符串 key
进行「减少计数」或「缩小计数」时,先在哈希表中看 key
是否存在:
-
若存在:依据其所属的
Node
的计数cnt
为多少,并联合以后是「减少计数」还是「缩小计数」来决定是找Node
的「右节点」还是「左节点」,同时查看相邻节点的计数值cnt
是否为目标值,对应要查看数值是 $cnt + 1$ 和 $cnt – 1$:- 若相邻节点的
cnt
为目标值:即指标节点存在,将key
从原Node
的set
汇合中移除,并增加到指标节点的汇合中,更新哈希表; - 若相邻节点的
cnt
不是目标值:则须要创立相应的指标节点,并构建双向链表关系,把key
存入新创建的指标节点,更新哈希表。
- 若相邻节点的
-
若不存在(只能是
inc
操作):查找是否存在 $cnt = 1$ 的节点(也就是查看hh.right
节点的计数值):- 如果存在 $cnt = 1$ 的指标节点:将
key
增加到指标节点的set
汇合中,更新哈希表; - 若不存在 $cnt = 1$ 的指标节点:创立相应的节点,并构建双向关系,并构建双向链表关系,把
key
存入新创建的指标节点,更新哈希表。
- 如果存在 $cnt = 1$ 的指标节点:将
getMaxKey/getMinKey
操作:别离从 tt.left
和 hh.right
中尝试查找,如果存在非哨兵节点,则从节点的 set
汇合中取任意元素进行返回,否则返回空串。
最初,为了确保 getMaxKey/getMinKey
操作可能严格 $O(1)$,咱们在进行 inc/dec
操作时咱们须要对一些 set
容量为 $0$ 的节点进行开释,即解除其所在双向链表的关系。
代码:
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(n)$
最初
这是咱们「刷穿 LeetCode」系列文章的第 No.432
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,局部是有锁题,咱们将先把所有不带锁的题目刷完。
在这个系列文章外面,除了解说解题思路以外,还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
为了不便各位同学可能电脑上进行调试和提交代码,我建设了相干的仓库:https://github.com/SharingSource/LogicStack-LeetCode。
在仓库地址里,你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉
本文由 mdnice 多平台公布