[leetcode] 432. 全 O(1) 的数据结构 | STL 双向链表&哈希

简介: 我们可以维护一个链表,这个链表是一个双向的,把这个链表维护成从头节点到尾节点是单调递增的,然后我们就可以很好的通过头尾返回出现次数最多(尾部)和出现次数最小的字符串(头部)在这个链表里面,我们存入两个部分,用 pair 做在一起,第一部分是存放 string 的 unorderedset 容器 keys,用来放置字符串,然后我们用第二部分来标识这个字符串出现的次数 count对于一个给定的字符串,如果不用遍历的防止获取他的位置,那还能怎么做呢?

题目链接


593e902e5eab48b1b4d351bca4fad5b1.png

之前没有做过这种类型的题目,看到的时候一脸蒙圈

看了官方题解之后,了解到这个是双向链表

然后来写一下题解:


我们可以维护一个链表,这个链表是一个双向的,把这个链表维护成从头节点到尾节点是单调递增的,然后我们就可以很好的通过头尾返回出现次数最多(尾部)和出现次数最小的字符串(头部)

在这个链表里面,我们存入两个部分,用 pair 做在一起,第一部分是存放 string 的 unorderedset 容器 keys,用来放置字符串,然后我们用第二部分来标识这个字符串出现的次数 count

对于一个给定的字符串,如果不用遍历的防止获取他的位置,那还能怎么做呢?

:用一个哈希表 nodes,用来标识每个字符串的位置,我们这里可以用STL中的unorderedmap<>,键就是字符串string,而值是列表的迭代器,list<p>::iterator


  1. 然后对于 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 所处的节点


  1. 对于 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 人正在系统学习中


目录
相关文章
|
19天前
【力扣】-- 移除链表元素
【力扣】-- 移除链表元素
31 1
|
4天前
|
存储 C语言
【数据结构】手把手教你单链表(c语言)(附源码)
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构,每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作,如头插、尾插、头删、尾删、查找、指定位置插入和删除等,并提供了完整的C语言代码示例。通过学习单链表,可以更好地理解数据结构的底层逻辑,提高编程能力。
25 4
|
5天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
5天前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法
|
24天前
|
算法 Java
数据结构与算法学习五:双链表的增、删、改、查
双链表的增、删、改、查操作及其Java实现,并通过实例演示了双向链表的优势和应用。
15 0
数据结构与算法学习五:双链表的增、删、改、查
|
4天前
|
C语言
【数据结构】双向带头循环链表(c语言)(附源码)
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点:双向、带头和循环。与单链表相比,它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1),提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现,包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
16 0
|
18天前
|
存储
[数据结构] -- 双向循环链表
[数据结构] -- 双向循环链表
17 0
|
24天前
|
存储
探索数据结构:便捷的双向链表
探索数据结构:便捷的双向链表
|
24天前
|
存储
探索数据结构:单链表的实践和应用
探索数据结构:单链表的实践和应用
|
24天前
|
算法 Java
数据结构与算法学习六:单向环形链表应用实例的约瑟夫环问题
这篇文章通过单向环形链表的应用实例,详细讲解了约瑟夫环问题的解决方案,并提供了Java代码实现。
15 0