考点
- 哈希表与链表的综合
- 掌握迭代器、
pair、unordered_set与unordered_map的本质
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
| class AllOne {
private:
list <pair<int, unordered_set<string> > > l;
unordered_map <string, list <pair<int, unordered_set<string> > >::iterator> m;
public:
AllOne() {}
void inc(string key) {
auto it = m.find(key);
if (it == m.end()) {
if (l.empty() || l.front().first > 1) {
l.emplace_front(1, unordered_set<string> {key});
} else {
l.front().second.emplace(key);
}
m[key] = l.begin();
} else {
auto node = it->second, nextNode = next(node);
if (nextNode == l.end() || nextNode->first > node->first + 1) {
m[key] = l.emplace(nextNode, node->first + 1, unordered_set<string> {key});
} else {
nextNode->second.emplace(key);
m[key] = nextNode;
}
node->second.erase(key);
if (node->second.empty()) l.erase(node);
}
}
void dec(string key) {
auto node = m[key], prevNode = prev(node);
if (node->first != 1) {
if (node == l.begin() || prevNode->first < node->first - 1) {
m[key] = l.emplace(node, node->first - 1, unordered_set<string> {key});
} else {
prevNode->second.emplace(key);
m[key] = prevNode;
}
} else {
m.erase(key);
}
node->second.erase(key);
if (node->second.empty()) l.erase(node);
}
string getMaxKey() {
return l.empty() ? "" : *(l.back().second.begin());
}
string getMinKey() {
return l.empty() ? "" : *(l.front().second.begin());
}
};
|
思路
本题难度极高，对哈希表、链表、迭代器的熟练度都是极大的考验，是非常棒的综合题！
在完成本题前，请先完成460. LFU 缓存与146. LRU 缓存，掌握基本的哈希表与链表的结合思路
题目希望给每个字符串计数，可增可减，所有操作为常数时间复杂度；并返回计数最大与最小的字符串，如果计数为0，则将其删除
可以参考LFU，只使用变量来记录极值吗？
LFU是单向操作，只增无减，统计极值用变量即可胜任
本题有增有减，只用变量很难记录空间的动态变化，必须依赖容器来完成这一操作
可以参考LFU的数据结构吗？
若参考LFU，使用unordered_map，则键为次数，给每个键单独新建链表作为值
那么只能用变量来记录键的极值，因为unordered_map是无序的，方才提过用变量是死路
若使用map，键虽有序但达不到常数时间复杂度
故而LFU的数据结构无法照搬
联想LRU用到的有序双向链表技巧，表头是最晚访问元素，表尾是最早访问元素，极值就在两侧
可以设计数据结构如下：
新建一个双向链表，链表节点为键值对，键为次数，值为unordered_set以存储字符串
次数增加，则在当前节点之后新增节点/修改下一个节点；次数减少，则在当前节点之前新增节点/修改前一个节点
从而保证了链表表头为次数最小值，链表表尾为次数最大值
新建一个哈希表，键为字符串，值为对应次数的链表节点地址
为什么设计“左小右大”？而不是像LRU一样”左大右小“？
若是左大右小，每次新增的节点都将在链表表尾，返回表尾元素的迭代器则是rbegin方法，且这个迭代器是reverse_iterator类型
reverse_iterator类型是对iterator类型的封装，可参见
双向链表list删除节点时，使用的是erase方法，它只支持iterator类型参数
返回表头元素迭代器的方法begin，满足这一条件。故而选择左小右大
为什么双向链表的节点不选择unordered_map，而选择pair?
因为unordered_map与map都没有取出键这一个操作，哈希表的意义就是通过键访问值
实际上，我们需要的是一个类似结构体的容器，第一个元素存储次数，第二个元素存储unordered_set
这样一来前后节点比较次数时，直接取节点容器的第一个元素对比即可
pair恰好满足，当然你乐意的话可以自写结构体
为什么存储字符串选择unordered_set，而不是vector？
因为字符串在不同节点之间转移时，所经历的步骤就是
- 从原节点存储删除
- 插入新节点存储
知道一个值，怎么在常数时间复杂度从存储中删除呢？只有哈希表了！
哈希表当中键与值相等的是什么STL？当然是unordered_set和set