专栏首页Michael阿明学习之路程序员面试金典 - 面试题 17.07. 婴儿名字(并查集)

程序员面试金典 - 面试题 17.07. 婴儿名字(并查集)

1. 题目

每年,政府都会公布一万个最常见的婴儿名字和它们出现的频率,也就是同名婴儿的数量。 有些名字有多种拼法,例如,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

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/baby-names-lcci 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

2. 解题

相关题目: LeetCode 959. 由斜杠划分区域(并查集) LeetCode 1202. 交换字符串中的元素(并查集)

class Solution {
    unordered_map<string,string> father;//并查集
    unordered_map<string,int> m;//名称,频次
public:
    vector<string> trulyMostPopular(vector<string>& names, vector<string>& synonyms) {
        string name, name1, name2, p;
        int i, count;
        for(string& n : names)
        {
            i = n.find("(");
            name = n.substr(0,i);
            count = 0;
            while(++i < n.size()-1)
                count = 10*count+n[i]-'0';
            m[name] = count;//获取每个名字的次数
            father[name] = name;//并查集初始化
        }
        for(auto& n : synonyms)
        {   //这里可能有上面不存在的name,再添加一遍
            i = n.find(",");
            name1 = n.substr(1,i-1);
            name2 = n.substr(i+1,n.size()-i-2);
            father[name1] = name1;//并查集初始化
            father[name2] = name2;//并查集初始化
        }
        for(auto& n : synonyms)
        {
            i = n.find(",");
            name1 = n.substr(1,i-1);
            name2 = n.substr(i+1,n.size()-i-2);
            merge(name1,name2);//全部进行合并和路径压缩
        }
        unordered_map<string,vector<string>> fatherSet;
        for(auto f : father)//压缩后的f(只有两层),所有边的顶层(字典序最小的)
        {
            name = f.first;
            p = uniFind(name);
            fatherSet[p].push_back(name);
        }
        vector<string> ans;
        for(auto& f : fatherSet)
        {	//所有的等效名字
            count = 0;
            for(auto& v : f.second)//它底下包含的name
                count += m[v];//加上他的计数
            ans.push_back(f.first+"("+to_string(count)+")");
        }
        return ans;
    }

    string uniFind(string x)
    {
        if(x == father[x])
            return x;
        return father[x] = uniFind(father[x]);//等式为路径压缩操作
    }

    void merge(string x, string y)
    {
        string fatherx = uniFind(x);
        string fathery = uniFind(y);
        if(fatherx != fathery)
        {
            if(fatherx < fathery)
                swap(fatherx, fathery);//x的字典序大
            father[fatherx] = fathery;//字典序小的y做代表
        }
    }
};

写的比较差,效率比较低

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 93. 复原IP地址(回溯)

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/restore-ip-addresses 著作权归领...

    Michael阿明
  • LeetCode 267. 回文排列 II(回溯)

    给定一个字符串 s ,返回其通过重新排列组合后所有可能的回文字符串,并去除重复的组合。

    Michael阿明
  • LeetCode 937. 重新排列日志文件(自定义排序)

    我们将这两种日志分别称为字母日志和数字日志。保证每个日志在其标识符后面至少有一个字。

    Michael阿明
  • # python # # Challenge # Level 2

    滚神大人
  • 游戏思维开发社区问答系统的感受

    大家好,最近在开发社区的问答系统,公众账号文章由于志愿者相继有事情,近期就更新的比较少,请大家见谅。本篇给大家讲讲社区系统的部分功能说明,后面必然开源,。

    李海彬
  • 『Go 内置库第一季:strings』

    这一季的系列主题,主要围绕内置库进行。如果一个人写的代码比你的赞,那么他对内置库的熟悉程度一定比你强。

    谢伟
  • mipush的receiver无法获得消息,断点也失效,原因很奇葩strings.xml缺少内容

    mipush的receiver无法获得消息,断点也失效,原因很奇葩strings.xml缺少内容

    战神伽罗
  • 摩斯码编解码器

      今天是1024,程序员节那就干点儿程序员的事情。刚好,记得上高中时候,看过一部电影,无间道,里边黄秋生和梁朝伟用摩斯码通信,瞬间觉得好神秘,好帅气。最近闲来...

    guokun
  • Go基础——字符串

    字符串结构由两个信息组成:第一个是字符串指向的底层字节数组,第二个是字符串的字节的长度。字符串其实是一个结构体,因此字符串的赋值操作也就是reflect.Str...

    羊羽shine
  • 记录一个发邮件的cs文件

    /* ---------------------------------      *     E-mail 发送接口      *     调用示例     ...

    用户1172164

扫码关注云+社区

领取腾讯云代金券