之前没有做过这种类型的题目，看到的时候一脸蒙圈
看了官方题解之后，了解到这个是双向链表
然后来写一下题解：
我们可以维护一个链表，这个链表是一个双向的，把这个链表维护成从头节点到尾节点是单调递增的，然后我们就可以很好的通过头尾返回出现次数最多(尾部)和出现次数最小的字符串(头部)
在这个链表里面，我们存入两个部分，用 pair 做在一起，第一部分是存放 string 的 unorderedset 容器 keys，用来放置字符串，然后我们用第二部分来标识这个字符串出现的次数 count
对于一个给定的字符串，如果不用遍历的防止获取他的位置，那还能怎么做呢？
：用一个哈希表 nodes，用来标识每个字符串的位置，我们这里可以用STL中的unorderedmap<>，键就是字符串string，而值是列表的迭代器，list<p>::iterator
- 然后对于 inc 操作来说：
如果当前字符串不在链表中，并且链表为空或者是头节点的字符串出现的次数大于1的时候，先插入一个 count=1 的新节点至链表的头部，然后将字符串插画如到头结点的keys中
如果说当前字符串key在链表当中，并且所在链表节点位置为 cur，如果说 cur.next 为空或者是c u r . n e x t . c o u n t > c u r . c o u n t + 1 ，那么说我们插入一个count=cur.count+1 的新节点至 cur 之后，然后将 key 插入到c u r . n e x t . k e y s 中，最后再将 key 从 cur.keys 中移除，如果说一处之后 cur.keys 为空，那么就将 cur 从链表中移除掉
然后更新 nodes 中 key 所处的节点
- 对于 dec
如果说 key 只出现了一次，那么说 −1 之后就变成了0，就要被移除
如果说出现了不止一次，那么就找到 key 所在节点 cur，如果说 cur.prev 为空或者是 cur.prev.count<cur.count-1 ，则先插入一个 count=cur.count−1 的新节点到 cur 之前，然后将 key 插入到 cur.prev.keys 中。然后最后更新我们的哈希表 nodes 中的当前字符串所处的节点，一共下次使用
最后，我们将当前字符串从 cur.keys 中移除掉，如果说 cur.keys 为空了，就直接将 cur删掉即可
Code:
class AllOne { typedef pair<unordered_set<string>,int> p; list<p> lst; unordered_map<string,list<p>::iterator> nodes; public: AllOne() { } void inc(string key) { if(nodes.count(key)) { auto cur = nodes[key]; auto nex = next(cur); if(nex == lst.end() || nex->second > cur->second+1) { unordered_set<string>s({key}); nodes[key] = lst.emplace(nex,s,cur->second+1); } else { nex->first.emplace(key); nodes[key] = nex; } cur->first.erase(key); if(cur->first.empty()) lst.erase(cur); } else {// not in list if(lst.empty() || lst.begin()->second > 1) { unordered_set<string>s({key}); lst.emplace_front(s,1); } else { lst.begin()->first.emplace(key); } nodes[key] = lst.begin(); } } void dec(string key) { auto cur = nodes[key]; if(cur->second == 1) { nodes.erase(key); } else { auto pre = prev(cur); if(cur == lst.begin() || pre->second < cur->second - 1) { unordered_set<string> s({key}); nodes[key] = lst.emplace(cur,s,cur->second - 1); } else { pre->first.emplace(key); nodes[key] = pre; } } cur->first.erase(key); if(cur->first.empty()) lst.erase(cur); } string getMaxKey() { if(lst.empty()) return ""; else return *lst.rbegin()->first.begin(); } string getMinKey() { if(lst.empty()) return ""; else return *lst.begin()->first.begin(); } }; /** * Your AllOne object will be instantiated and called as such: * AllOne* obj = new AllOne(); * obj->inc(key); * obj->dec(key); * string param_3 = obj->getMaxKey(); * string param_4 = obj->getMinKey(); */
文章知识点与官方知识档案匹配，可进一步学习相关知识
算法技能树leetcode-链表82-删除排序链表中的重复元素 II8256 人正在系统学习中
