---

一、面试题 17.07. 婴儿名字

面试题 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)”]

leetcode面试题 17.07 java

思路

并查集 名字-parent，次数-size

find，寻找每个名字的父节点

将父节点一样的name，次数相加

class Solution {
    public String[] trulyMostPopular(String[] names, String[] synonyms) {
        UnionFind uf = new UnionFind();
        for(String name:names){
            int idx1 = name.indexOf('(');
            int idx2 = name.indexOf(')');
            String new_name = name.substring(0,idx1);
            int fre = Integer.valueOf(name.substring(idx1+1,idx2));
            uf.parent.put(new_name,new_name);
            uf.size.put(new_name,fre);
        }
        for(String syn:synonyms){
            int idx = syn.indexOf(',');
            String name1 = syn.substring(1,idx);
            String name2 = syn.substring(idx+1,syn.length()-1);
            //初始化
            if(!uf.parent.containsKey(name1)){
                uf.parent.put(name1,name1);
                uf.size.put(name1,0);
            }
            if(!uf.parent.containsKey(name2)){
                uf.parent.put(name2,name2);
                uf.size.put(name2,0);
            }
            uf.union(name1,name2);
        }

        //System.out.println(uf.size);

        List<String> res = new ArrayList<>();
        for(String name:names){
            int idx1 = name.indexOf('(');
            String new_name = name.substring(0,idx1);
            if(new_name.equals(uf.find(new_name))){
                res.add(new_name+'('+uf.size.get(new_name)+')');
            }
        }
        return res.toArray(new String[res.size()]);
    }
    public class UnionFind{
        //父节点
        Map<String,String> parent;
        //人数
        Map<String,Integer> size;

        public UnionFind(){
            this.parent = new HashMap<>();
            this.size = new HashMap<>();
        }

        public String find(String x){
            if(parent.get(x).equals(x)) return x;
            parent.put(x,find(parent.get(x)));
            return parent.get(x);
        }

        public void union(String x, String y){
            String str1 = find(x), str2 = find(y);
            if(str1.equals(str2)) return;
            //如果str2字序小
            if(str1.compareTo(str2)>0){
                parent.put(str1,str2);
                size.put(str2,size.get(str1)+size.get(str2));
            } else {
                parent.put(str2,str1);
                size.put(str1,size.get(str1)+size.get(str2));
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

---

总结