map与set容器初识:初步运用map与set

前言:

本文主要讲解的时对于map与set容器的初步使用,希望大家对map与set容器不熟悉的看了之后可以快速运用set与map到日常中来。(本文适合对vector等基础容器有一定基础的同学)

一、set与map容器常见接口

迭代器接口与以往的所有容器一样,同样的构造方法,同样的名称。

empty判断容器是否为空,size返回当前容器的大小,max_size返回容器的最大大小是多少,我们常用的是前两个接口,max_size一般情况下不会接触。 

值得一提是map容器的operator[],这个函数在调用时服用了insert的功能,当当前key值的元素不存在时,会插入一个当前键值元素,并返回新插入的元素地址。如果存在该key值,就返回该key值的地址。

二者都用insert函数来插入,在学了右值引用后,也可以用emplace来进行插入工作(操作与insert一样)。

之后的clear清空容器,swap交换两个容器内容,erase删除某个元素的操作都与其他容器差不多,包括find查找,count判断有无。要注意的是二者的范围查找接口,

对于二者的lower_bound(key); 都会返回第一个不小于 key 的迭代器。upper_bound(key); 都会返回第一个大于 key 的迭代器。

其实,在日常刷题做题中,我们的常用操作就是新建一个set或者mao容器,然后根据题目规则存储信息(set太棒用于去重排序,map用来记录两种数据之间的关联)在使用map时,我们也不会特地使用insert来进行插入,一般会直接在容器名后面[]键值,自动进行插入或者修改操作。

多说没用,实践才是最好的老师,接下来就让我带领大家做几道题应用一下map与set吧。

二 、实战运用

1、随机链表的复制

(题目链接:https://leetcode.cn/problems/copy-list-with-random-pointer/description/)

在没有学习map与set之前,我们是怎么解决这道题的呢?

对于这道题来讲,难点在于怎么深拷贝random 所指向的节点因为我们没有与之对应的映射关系。

以例1为例,当我们拷贝了一个新链表之后,新的13节点的random指针所指向的 7,我们是没有存储的信息的,也就是找不到新链表上的7的地址。为了解决这个问题,我们将新链表插入在老链表之间,比如老1,13之间夹着一个新7.通过让next指向新拷贝的结点,让二者产生联系。在分开链表之间,只需要通过pcur->next->random=pcur->random->next就能得到解决。

class Solution 
{
public:Node* copyRandomList(Node* head) {if (head == nullptr){return nullptr;}Node* cur = head;while (cur)//先复制节点并连接点原本链表中{Node* pcur = new Node(cur->val);pcur->next = cur->next;cur->next = pcur;cur = pcur->next;}cur = head;while (cur != nullptr){if (cur->random != nullptr){cur->next->random = cur->random->next;}else{cur->next->random = nullptr;}cur = cur->next->next;}Node* phead = head->next, * prew = head;cur = phead;while (cur){prew->next = cur->next;prew = prew->next;if (prew == nullptr){cur->next = nullptr;cur = cur->next;}else{cur->next = prew->next;cur = cur->next;}}return phead;}
};

但是在有了map之后,就不用这么麻烦。只需要新建一个map,key为老节点,val为新的对应节点,就可以轻松完成代码。

class Solution 
{
public:Node* copyRandomList(Node* head){map<Node*,Node*>Map;Node*cur=head,*copyhead=nullptr,*copytail=nullptr;while(cur)//cur遍历原链表进行拷贝并且把原链表与拷贝链表一一插入进map{if(copytail==nullptr){copyhead=copytail=new Node(cur->val);}else{copytail->next=new Node(cur->val);copytail=copytail->next;}Map[cur]=copytail;cur=cur->next;}cur=head;Node* copy=copyhead;while(cur){if(cur->random==nullptr){copy->random=nullptr;}else{copy->random=Map[cur->random];//直接从map表中找到相应的节点地址}cur=cur->next;copy=copy->next;}return copyhead;}
};

2、环形链表2

(题目链接:https://leetcode.cn/problems/linked-list-cycle-ii/solutions/441131/huan-xing-lian-biao-ii-by-leetcode-solution/)

对于该题,在学习set与map之前我们通常用快慢指针法解决,由于数学原理与图形关系,倘若有环,快慢指针必定相遇 ,因此可以反向求出第一个入环节点的位置。

ListNode* hasCycle(struct ListNode* head)
{if (head == NULL || head->next == NULL)//当传过来的链表是空链表,或者传来的只有一个节点,且指向为空,说明不是环{return NULL;//返回false}ListNode* pcur = head, * ptail = head;while (ptail->next && ptail->next->next)//ptail->next与ptail->next->next其中有一个为假,就说明该指针有尽头,不是环{ptail = ptail->next->next;//快慢指针,如果相遇了,说明必有环,不相遇则一定有尽头pcur = pcur->next;if (ptail == pcur){return ptail;//返回相遇点地址}}return NULL;
}struct ListNode* detectCycle(struct ListNode* head){//如果有环,先找到相遇点ListNode* meet = hasCycle(head);if (meet == NULL){return NULL;}//说明有环//快指针速度为慢指针两倍,快指针所走的路程为慢指针两倍,画出路程图可以列出关系式:当fast从相遇点出发,slow从head出发,速度相同,路程相同//会同时到达第一个相交节点ListNode* slow = head;while (slow != meet){slow = slow->next;meet = meet->next;}return meet;}

但我们现在可以用set来记录出现过的链表节点,轻松解决问题。

class Solution 
{
public:ListNode *detectCycle(ListNode *head) {set<ListNode *>Set;ListNode*ret=nullptr,*cur=head;while(cur){bool Find=Set.insert(cur).second;if(Find==false){ret=cur;break;}cur=cur->next;}return ret;}
};

二者代码复杂度一看便知。

3、前K个高频单词

(题目链接:https://leetcode.cn/problems/top-k-frequent-words/description/)

在我们看见第k大,前k个这样的关键字时,我们就想到了这是一个topk问题,自然也可以用优先级队列解决。但我们这里可以结合map的性质,与仿函数相结合解决问题。

我们可以用一个一个 map<string, int> Map,用于统计每个单词的出现次数。string 是单词,int 是该单词的出现频率。

随后使用 for (auto it : words) 遍历 words 数组,对于每个单词,将其频率在 Map 中加 1。这个循环完成后,Map 中存储了每个单词对应的出现频率。

接下来再缔造一个vector<pair<string, int>>,用来我们对pair进行排序,所以我们要添加仿函数来排序pair对象。

class Solution
{
public:struct Compare{bool operator()(const pair<string, int>& a, const pair<string, int>& b){/*return a.second > b.second || (a.second == b.second && a.first < b.first);*/return a.second > b.second ;}};vector<string> topKFrequent(vector<string>& words, int k){map<string, int>Map;vector<string>ret;for (auto it : words){Map[it]++;}vector<pair<string, int>>arr(Map.begin(), Map.end());/*   sort(arr.begin(), arr.end(), Compare());*/stable_sort(arr.begin(), arr.end(), Compare());for (int i = 0; i < k; ++i){ret.push_back(arr[i].first);}return ret;}
};

我这里的代码结合了map本身对key键值对就进行了字典序排序,所以我们后面才使用稳定的stable_sort,这样就算两个key的val相同,二者的字典序相对顺序也不会改变。。如果我们要使用sort,就需要在仿函数中加上对val值相同,比较字典序的判断条件。

4、单词识别

(题目链接;http://https://www.nowcoder.com/practice/http://https://www.nowcoder.com/practice/)

对与此题,我们也可以类似的用map来存储单词与出现频率的关系。

为了能够接受一句话,所以我们要用getline来接受而不是cin。

#include <iostream>
using namespace std;
#include<map>
#include<algorithm>
#include<string>
#include<vector>struct Compare
{bool operator()(const pair<string,int>&a,const pair<string,int>&b){return a.second>b.second;}
};int main()
{string s;map<string,int>Map;getline(cin,s);char*ch;for(int i=0;i<s.size();++i){string ss;while(s[i]!=' '){if(s[i]=='.'){break;}ss+=tolower(s[i++]);}Map[ss]++;}vector<pair<string,int>>arr(Map.begin(),Map.end());stable_sort(arr.begin(),arr.end(),Compare());for(auto it:arr){cout<<it.first<<":"<<it.second<<endl;}return 0;
}

三、总结

在本文中,我们通过多个实际例题,深入探讨了 mapset 容器的常见操作和实际应用。这些容器在处理数据的过程中能够提供强大的支持,尤其在涉及到元素的唯一性、快速查找和数据关联的场景下。

1. 基本操作与接口

我们首先回顾了 mapset 容器的基本操作,包括元素插入、查找、删除等常用接口。在日常的算法题解中,这些基本操作为我们提供了便捷的工具。例如,使用 map 记录元素之间的关联关系,利用 set 处理去重和排序问题。

2. 实战应用

我们通过几个经典的算法题,展示了如何在实际编程中运用 mapset 容器。通过这些案例,我们看到了这些容器在不同场景下的灵活性和高效性:

  • 随机链表的复制:利用 map 建立新旧节点之间的映射关系,简化了链表的深拷贝操作。
  • 环形链表检测:通过 set 记录已经访问过的节点,轻松找到链表中的环。
  • 前K个高频单词:结合 map 统计频率和仿函数排序,快速找到出现频率最高的单词。
  • 单词识别:使用 map 统计句子中每个单词的频率,并按出现次数进行排序,展示了 map 的实用性。
3. 稳定排序的应用

在排序过程中,我们强调了 stable_sort 的使用,这对于保持排序的稳定性尤为重要。在某些题目中,我们需要确保排序过程中,相同频率的单词按字典序排列,而 stable_sort 正是保证这种稳定性的关键。

4. 代码复杂度与性能

通过与传统方法的比较,我们可以看到使用 mapset 后,代码复杂度得到了简化,逻辑更为清晰。虽然这些容器的底层实现较为复杂,但它们提供的高效查找和插入性能,使得我们在解决实际问题时受益匪浅。

结语

学习 mapset 容器不仅仅是掌握其基本用法,更重要的是通过实践,理解它们在不同场景中的应用和优势。本文的示例和解析,希望能帮助读者更好地掌握这些工具,并在今后的算法和编程实践中更加得心应手。通过不断练习,读者可以熟练地将 mapset 应用于各种复杂的数据处理任务中,从而提升编程效率和代码质量。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/405832.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

12 程序控制语句:循环控制(while、do-while、for、多重嵌套循环、死循环)

目录 1 while 循环 1.1 基本语法 1.2 流程图 1.3 计数循环 1.3.1 实现原则 1.3.2 案例&#xff1a;循环输出语句 1.3.3 案例&#xff1a;循环输出数字 7~15 1.3.4 案例&#xff1a;倒序输出数字 56 ~ 43 1.3.5 案例&#xff1a;输出 10&#xff08;包括 10&…

使用 Go 语言将 Base64 编码转换为 PDF 文件

使用Go语言将PDF文件转换为Base64编码-CSDN博客文章浏览阅读104次&#xff0c;点赞2次&#xff0c;收藏5次。本文介绍了如何使用 Go 语言将 PDF 文件转换为 Base64 编码&#xff0c;并保存到文件中。https://blog.csdn.net/qq_45519030/article/details/141224319 在现代编程中…

【WebSocket】websocket学习【二】

1.需求&#xff1a;通过websocket实现在线聊天室 2.流程分析 3.消息格式 客户端 --> 服务端 {"toName":"张三","message":"你好"}服务端 --> 客户端 系统消息格式&#xff1a;{"system":true,"fromName"…

SQL注入(head、报错、盲注)

目录 【学习目标、重难点知识】 【学习目标】 【重难点知识】 1. 报错注入 1.1 那么什么是报错注入呢&#xff1f; 1.2 报错注入原理 extractvalue函数 updatexml函数 1.3 靶场解析 靶场练习 2. HEAD注入 2.1 相关全局变量 2.2 靶场解析 burp暴力破解 靶场练习 3…

Spring核心思想讲解之控制反转(IOC)

控制反转概述 控制反转实现方式 XML方式 方式一 方式二 方式三 注解方式 第一步 第二步 第三步 依赖注入&#xff08;DI&#xff09;实现方式 XML方式 手动注入 set注入 构造器注入 自动注入 set注入 构造方法注入 注解方式 方式一&#xff1a; 方式二&…

Transformer模型中的Position Embedding实现

引言 在自然语言处理&#xff08;NLP&#xff09;中&#xff0c;Transformer模型自2017年提出以来&#xff0c;已成为许多任务的基础架构&#xff0c;包括机器翻译、文本摘要和问答系统等。Transformer模型的核心之一是其处理序列数据的能力&#xff0c;而Position Embedding在…

python之matplotlib (1 介绍及基本用法)

介绍 matplotlib是Python中的一个绘图库&#xff0c;它提供了一个类似于 MATLAB 的绘图系统。使用matplotlib你可以生成图表、直方图、功率谱、条形图、错误图、散点图等。matplotlib广泛用于数据可视化领域&#xff0c;是 Python 中最著名的绘图库之一。 同样matplotlib的安…

Java数组怎么转List,Stream的基本方法使用教程

Stream流 Java 的 Stream 流操作是一种简洁而强大的处理集合数据的方式,允许对数据进行高效的操作,如过滤、映射、排序和聚合。Stream API 于 Java 8 引入,极大地简化了对集合(如 List、Set)等数据的处理。 一、创建 Stream 从集合创建: List<String> list = Ar…

NGINX 之 location 匹配优先级

章节 1 NGINX 的源码安装 2 NGINX 核心配置详解 3 NGINX 之 location 匹配优先级 4 NGINX 基础参数与功能 目录 1 location 基础语法 1.1 location 语法说明表 1.2 URI部分简单介绍 2 location 匹配优先级 2.1 URI匹配的规则与顺序 2.2 精确匹配(location /1.txt) 2.3 区…

Python个人收入影响因素模型构建:回归、决策树、梯度提升、岭回归

全文链接&#xff1a;https://tecdat.cn/?p37423 原文出处&#xff1a;拓端数据部落公众号 “你的命运早在出生那一刻起便被决定了。”这样无力的话语&#xff0c;无数次在年轻人的脑海中回响&#xff0c;尤其是在那些因地域差异而面临教育资源匮乏的年轻人中更为普遍。在中国…

企业级WEB应用服务器——TOMCAT

一、WEB技术 1.1、HTTP协议和B/S 结构 最早出现了CGI&#xff08;Common Gateway Interface&#xff09;通用网关接口&#xff0c;通过浏览器中输入URL直接映射到一个 服务器端的脚本程序执行&#xff0c;这个脚本可以查询数据库并返回结果给浏览器端。这种将用户请求使用程…

AWS不同类型的EC2实例分别适合哪些场景?

Amazon Web Services&#xff08;AWS&#xff09;的弹性计算云&#xff08;EC2&#xff09;提供了多种实例类型&#xff0c;以满足不同的应用需求和工作负载。了解不同类型的 EC2 实例及其适用场景&#xff0c;可以帮助用户更好地优化性能和控制成本。九河云和大家一起了解一下…

安恒信息总裁宋端智,辞职了!活捉一枚新鲜出炉的餐饮人!

吉祥知识星球http://mp.weixin.qq.com/s?__bizMzkwNjY1Mzc0Nw&mid2247485367&idx1&sn837891059c360ad60db7e9ac980a3321&chksmc0e47eebf793f7fdb8fcd7eed8ce29160cf79ba303b59858ba3a6660c6dac536774afb2a6330#rd 《网安面试指南》http://mp.weixin.qq.com/s?…

I/O模型

文章目录 I/O模型相关概念网络I/O模型阻塞型I/O模型非阻塞型I/O模型多路复用I/O型信号驱动式I/O型异步I/O模型 apache和nginx的区别&#xff0c;什么时候选择apache&#xff0c;什么时候选择nginx 文章相关连接如下&#xff1a; 如果想更多了解nginx&#xff0c;请点击&#x…

为什么要使用TikTok云手机

随着TikTok平台的日益繁荣&#xff0c;TikTok云手机作为一种新兴的运营工具&#xff0c;正以其独特的云端技术和用户体验&#xff0c;赢得广大用户的青睐。相较于传统手机&#xff0c;TikTok云手机通过云端技术为用户带来了一系列新的优势&#xff0c;让TikTok运营变得更加灵活…

涂料耐久性氙灯老化试验箱

涂料氙灯老化试验箱是现代检测手段中常用的一种设备&#xff0c;它能够模拟自然光照、光照老化等环境条件&#xff0c;对涂料、染料、塑料、橡胶、纺织品、涂层等材料进行老化试验&#xff0c;以评估其耐久性和使用寿命。本文将详细介绍涂料氙灯老化试验箱的工作原理、使用注意…

正则表达式——详解

正则表达式是什么&#xff1f; 正则表达式&#xff08;Regular Expression&#xff0c;通常简写为 regex、regexp 或 RE&#xff09;是一种强大的文本处理工具&#xff0c;用于描述一组字符串的模式。它可以用来匹配、查找、替换等操作&#xff0c;几乎所有现代编程语言都支持…

【流媒体】RTMPDump—RTMP_Connect函数(握手、网络连接)

目录 1. RTMP_Connect函数1.1 网络层连接&#xff08;RTMP_Connect0&#xff09;1.2 RTMP连接&#xff08;RTMP_Connect1&#xff09;1.2.1 握手&#xff08;HandShake&#xff09;1.2.2 RTMP的NetConnection&#xff08;SendConnectPacket&#xff09; 2.小结 RTMP协议相关&am…

2024计算机软考报名流程(电脑报名)

1.24年下半年软考报名时间&#xff0c;各省报名时间不一样&#xff0c; 报名时间大概集中在&#xff1a;24年8月19日&#xff5e;24年9月15日&#xff1b; 报名网站&#xff1a;中国计算机技术职业资格网&#xff1b; 广东&#xff1a;2024年8月21日9:00至29日17:00 安徽&#…

Vue3 的 expose 介绍

在 Vue 3 中&#xff0c;expose 是一个用于控制组件内部方法和属性暴露给父组件的新功能。这使得父组件可以调用子组件内部的方法或访问其数据&#xff0c;尤其在使用组合式 API&#xff08;Composition API&#xff09;时&#xff0c;这种能力非常有用。 1. 基本用法 expose…