【程序员面试金典】面试题 17.07. 婴儿名字

news/2024/10/31 0:13:42/

【程序员面试金典】面试题 17.07. 婴儿名字

    • 题目描述
    • 解题思路

题目描述

描述:每年,政府都会公布一万个最常见的婴儿名字和它们出现的频率,也就是同名婴儿的数量。有些名字有多种拼法,例如,John 和 Jon 本质上是相同的名字,但被当成了两个名字公布出来。给定两个列表,一个是名字及对应的频率,另一个是本质相同的名字对。设计一个算法打印出每个真实名字的实际频率。注意,如果 John 和 Jon 是相同的,并且 Jon 和 Johnny 相同,则 John 与 Johnny 也相同,即它们有传递和对称性。

在结果列表中,选择 字典序最小 的名字作为真实名字。

示例:

输入:names = ["John(15)","Jon(12)","Chris(13)","Kris(4)","Christopher(19)"], synonyms = ["(Jon,John)","(John,Johnny)","(Chris,Kris)","(Chris,Christopher)"]
输出:["John(27)","Chris(36)"]

提示:

names.length <= 100000

解题思路

思路1:最直观的想法是,并查集。首先遍历synonyms集合,其中每个synonym中的两个名字n1和n2属于同一个集合,故使用merge函数将n1和n2合并。merge函数实现方法:首先使用search方法分别找到n1、n2的根节点r1、r2,然后将较小的节点挂载在较大节点的父节点上,从而实现根节点为字典序较小的节点。search函数实现方法:如果集合中不包含该节点则将该节点初始化为自己的父节点,反之,如果当前节点父节点不为自己,则递归将父节点的父节点即根节点设为其父节点,并最后返回当前节点父节点即字典序最小节点即根节点。

unordered_map<string,string> ump;
//查找父节点
string search(string &name)
{//集合中不包含该节点则将该节点初始化为其父节点if(ump.count(name)==0)return ump[name]=name;//如果当前节点父节点不为自己 则将父节点的父节点设为其父节点if(ump[name]!=name)ump[name]=search(ump[name]);//返回当前节点父节点即字典序最小节点return ump[name];
}
//将同名格式转换为set格式
//"(Jon,John)","(John,Johnny)" —— Jon,John,Johnny
void merge(string &n1,string &n2)
{//找n1所在集合代表节点string r1=search(n1);//找n2所在集合代表节点string r2=search(n2);//选择代表节点字典序最小的if(r1<r2)ump[r2]=r1;else if(r1>r2)ump[r1]=r2;
}
vector<string> trulyMostPopular(vector<string>& names, vector<string>& synonyms) 
{for(auto synonym:synonyms){int inx1=synonym.find("(");int inx2=synonym.find(",");int inx3=synonym.find(")");auto n1=string(synonym.begin()+inx1+1,synonym.begin()+inx2);auto n2=string(synonym.begin()+inx2+1,synonym.begin()+inx3);//选择字典序较小的作为真实名字merge(n1,n2);}unordered_map<string,int> mp;//将字符串格式转换为键值对格式 //"John(15)" —— John:15for(auto name:names){int pos1=name.find("(");int pos2=name.find(")");auto k=string(name.begin(),name.begin()+pos1);auto v=stoi(string(name.begin()+pos1+1,name.begin()+pos2));//查找每一个名字的根名字mp[search(k)]+=v;}vector<string> res;for(auto n:mp){string s=n.first+'('+to_string(n.second)+')';res.push_back(s);}return res;
}

总结:并查集的本质是一棵树,即同一集合的元素均位于一棵树上,两个元素在同一集合即两个元素所在树的树根相同。本题处理字符串也较为繁琐,但是需要注意,C++中可以使用find函数定位所需查找的分割符位置,然后使用迭代器begin()、end()来获取具体元素。


http://www.ppmy.cn/news/598411.html

相关文章

linux 安装 Microsoft Edge 卡顿问题解决(刷新率低)

问题描述 使用linux操作系统安装 Microsoft Edge 浏览器感觉刷新率低&#xff0c;每次滑动页面一顿一顿的 解决方案 系统性能–使用硬件加速(如可用)–关闭或打开 我这里是关闭之后重启浏览器就好了

使用poi3.15对Excel工作簿进行分割

public void setSheetForPrint(Workbook workbook)throws Exception{/*** 处理顺序:* 1 确定现有页数,并保存 以待用于删除* 2 巡查工作簿1 获取终结列数和分割次数* 3 巡查工作簿1 并将其内容进行分割复制* 4 用第1步保存的页序号进行删除*//*1 确定现有页数,并保存 以待用于删…

Android——基本控件(下)(十五)

1. 对话框&#xff1a;Dialog 1.1 知识点 &#xff08;1&#xff09;掌握对话框的主要作用&#xff1b; &#xff08;2&#xff09;可以使用AlertDialog和AlertDialog.Builder进行对话框的建立&#xff1b; &#xff08;3&#xff09;可以通过LayoutInflater进行定制对话框…

netwox 基于 Ethernet 层构造 IP 数据包【网络工程】(保姆级图文)

目录 基于 Ethernet 层构造 IP 数据包1) 不指定选项&#xff0c;直接运行该模块&#xff0c;查看默认设置。执行命令如下&#xff1a;3) 验证构造的数据包&#xff0c;使用 Wireshark 工具捕获数据包&#xff0c;如图所示。其中&#xff0c;第 2 个数据包为构造的 IPv4 数据包。…

联想Lenovo Quick Fix:关闭或开启Win10系统的自动更新

禁止win10更新小工具.zip - 蓝奏云 下载链接&#xff1a;关闭Win10自动更新.exe - 蓝奏云

联想X86服务器重启管理控制器(XClarity Controller)或TSM的方法

当设备运行较长时间时&#xff0c;服务器的管理控制器&#xff08;或称服务处理器&#xff0c;Service Processor&#xff09;可能由于内存或空间等问题响应缓慢&#xff0c;如果机器上运行ESXi&#xff0c;有可能会在Vcenter报出部件的“state deassert”信息&#xff0c;如下…

联想电脑 linux BIOS,Lenovo笔记本BIOS中各个选项的中文含义是什么

操作步骤: Lenovo笔记本电脑进入BIOS方式: 方式一:按下电源开关按钮开机后,连续不断敲击键盘上的F2按键(频率:每秒1-2次); 方式二:按下电源开关按钮开机后,一边按下键盘左下角的Fn功能键,一边连续不断敲击键盘上的F2按键(频率:每秒1-2次); 方式三: 1、目前联想新销售…

按丶自动打开计算机,联想电脑台式机启动自动进入Lenovo diagnostics界面

用户找到电脑不能进入桌面,启动电脑总是显示这个界面,打开机箱盖子,发现硬件配置,还是独立显卡都很正常。灰尘也不多 ,配置也挺好。 总是进入这个界面,最后发现原来键盘的F10按键被按下去了, 这个台式机键盘比较生硬,容易卡主,灵敏度还行,一点键盘按键卡主,就系统总…