原创 [并查集]并查集应用之婴儿姓名

发布时间:2021-08-02 22:25:18 浏览 241 来源:猿笔记 作者:铜炉

    政府都会公布一万个最常见的婴儿名字和它们出现的频率,John和Jon本质上是相同的名字,一个是名字及对应的频率,另一个是本质相同的名字对,设计一个算法打印出每个真实名字的实际频率,选择字典序最小的名字作为真实名字,本题仍然是一道判断连通性的题目?不同姓名通过synonyms来表示了连通关系,因为最终的结果返回的是存在连通关系的姓名所对应数量的总和,使用并查集将存在连通关系的名字合并并存储。最终统计每颗树下的名字总量即可,本题中分量即为不同的名字,即并查集中每颗树的名字总量,如果两个名字判断相同,没有办法直接通过数组下标与数组值的关系来维护树的归属关系。


    今天我们继续平行搜索的应用培训

    ##题目

    【宝宝名字】(

    政府每年公布一万个最常见的婴儿名字及其出现频率,也就是同名婴儿的数量。有些名字有多种拼法。比如约翰和乔恩本质上是同一个名字,但是公布为两个名字。给定两个列表,一个是名字和对应的频率,另一个是本质上相同的名字对。设计一个算法打印出每个实名的实际频率。注意,如果约翰和乔恩是一样的,乔恩和约翰尼也是一样的,那么约翰和约翰尼也是一样的,即具有传递性和对称性。

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

    示例

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

    输出:["John(27)","Chris(36)"]

    ##分析

    这个题目还是判断连通性的题目。不同的名字通过同义词来表示连通度,因为最终的结果返回的是有连通度的名字所对应的数字的总和,所以有连通度的名字是利用搜索集来合并存储的,最终可以统计出每棵树下的名字总数。

    # # #以及如何使用本主题中的集合

    -重量是多少?

    本主题中的组件是不同的名称

    -结果返回了什么?

    标题要求具有相同名称的结果总数,即搜索集中每个树的名称总数

    # # #搜索集合中树的定义

    将具有合并关系的名称合并到一个树中应该会返回与最后一样多的结果。

    # # #合并操作的预判断

    在给定的同义词数组中,如果两个名称被判断为相同,则需要合并两个组件

    # # #注意第一点

    与过去相比,没有办法直接通过数组下标和数组值之间的关系来维护树的所有权关系,原因有二

    1,因为数组下标是整数,名字是String;

    2.全名的总数不能一次获得,需要遍历两个参数才能获得。

    因此,这里使用映射来维护父子关系

    # # #注意第二点

    树的父子关系不能简单地用权重来比较,而要用字符串的字典顺序来比较。在组合组件时,需要通过与字符串的方法进行比较来判断字段顺序。

    # # #注意第三点

    最终结果是返回每棵树的名称总数。自下而上搜索容易,自上而下搜索繁琐。因此,在合并操作中,名字的数量直接累积在根节点上,最终可以直接获得总数。

    # #解决问题的步骤

    1.对集合进行变换和搜索,通过两个映射来识别父子关系和名字对应的编号。

    2.解析名称,并将名称和名称数量初始化到搜索集中。

    3.解析同义词时,需要注意同义词中可能出现名称,需要在搜索集中进行判断和初始化。

    4.要合并有关联关系的名字,需要注意按照字典顺序建立父子关系。

    5.构建一个结果集,并返回根节点的名称和名称个数。

    # #代码编写

    ###并查集改造classtrulyMostPopularUnionFind{

    //因为是字符串组件,大小无法初始化,map用于存储

    Mapname2ParentNameMap;

    //存储组件名称的数量

    Mapname2NameCountMap;

    publictrulyMostPopularUnionFind(){

    //初始化分量map

    this.name2ParentNameMap=newHashMap<>();

    //初始化组件对应的mmap数量

    this.name2NameCountMap=newHashMap<>();

    }

    Stringfind(Stringname){

    if(name2ParentNameMap.get(name).equals(name))returnname;

    //路径压缩

    StringparentName=find(name2ParentNameMap.get(name));

    name2ParentNameMap.put(name,parentName);

    returnparentName;

    }

    voidunion(Stringname1,Stringname2){

    //找到组件对应的ID

    Stringp1=find(name1);

    Stringp2=find(name2);

    if(p1.equals(p2)){

    //如果两个组件在同一个树中,它们不需要合并

    return;

    }

    //使用字典顺序识别父子关系

    //同时,将组件对应的名称数量添加到父节点

    if(p1.compareTo(p2)<0){

    name2ParentNameMap.put(p2,p1);

    name2NameCountMap.put(p1,name2NameCountMap.get(p1)+name2NameCountMap.get(p2));

    }else{

    name2ParentNameMap.put(p1,p2);

    name2NameCountMap.put(p2,name2NameCountMap.get(p1)+name2NameCountMap.get(p2));

    }

    }

    intgetCount(Stringname){

    //返回父节点的名称个数

    StringparentName=find(name);

    returnname2NameCountMap.get(parentName);

    }

    publicMapgetName2ParentNameMap(){

    returnname2ParentNameMap;

    }

    publicvoidsetName2ParentNameMap(Mapname2ParentNameMap){

    this.name2ParentNameMap=name2ParentNameMap;

    }

    publicMapgetName2NameCountMap(){

    returnname2NameCountMap;

    }

    publicvoidsetName2NameCountMap(Mapname2NameCountMap){

    this.name2NameCountMap=name2NameCountMap;

    }

    }

    # # #算法代码编写

    classSolution{

    publicString[]trulyMostPopular(String[]names,String[]synonyms){

    trulyMostPopularUnionFinduf=newtrulyMostPopularUnionFind();

    ListtrueNameList=newArrayList<>();

    for(Stringname:names){

    intindexCountStart=name.indexOf('(');

    intindexCountEnd=name.indexOf(')');

    StringtrueName=name.substring(0,indexCountStart);

    trueNameList.add(trueName);

    intcount=Integer.valueOf(name.substring(indexCountStart+1,indexCountEnd));

    //初始化时,每个组件的父节点都指向自己

    uf.name2ParentNameMap.put(trueName,trueName);

    //初始化期间每个组件的名称数量

    uf.name2NameCountMap.put(trueName,count);

    }

    //关闭

作者信息

铜炉 [等级:3] Java
发布了 59 篇专栏 · 获得点赞 172 · 获得阅读 4060

相关推荐 更多