Today we will continue our training on the application of and look up sets

The title

The baby’s name

Every year, the government publishes the 10,000 most common baby names and their frequency, which is the number of babies with the same name. Some names have multiple spellings, for example, John and Jon are essentially the same name, but are published as two names. Given two lists, one of names and their corresponding frequencies, and the other of essentially identical pairs of names. Design an algorithm to print out the actual frequency of each real name. Note that if John and Jon are the same, and Jon and Johnny are the same, then John and Johnny are the same, i.e., they have transitivity and symmetry. In the result list, select the name with the smallest lexicographic order as the real name. Example input: names = ["John(15)","Jon(12)","Chris(13)","Kris(4)","Christopher(19)"], Synonyms = [(Jon, John) ", "(John and Johnny)", "(Chris, Kris)", "(Chris, Christopher)"] output: [" John (27) ", "Chris (36)"]Copy the code

Analysis of the

Connectivity is still a bear on the judgment of subject, different name by synonyms to represent the relationship between the connected, because the final result returned is connected between the name corresponds to the sum of the number, so the use and check there is a connected relationship sets the name of the merger and stored, and eventually total statistics every name under the tree.

How to use and query set in this problem

  • What are the components? In this case, the components are given different names
  • What does the result return?

They want the total number of results with the same name, that is, the total number of names for each tree in the set

And look up the definition of a set tree

Merge the merged names into a fallen tree and return as many results as there are trees.

Prejudgment of merge operation

In an array in which two names are identical, I am required to combine both entries

Pay attention to point a

In this case, there is no way to maintain tree ownership through the relationship between array subscripts and array values. There are two reasons: 1. 2. The total number of names cannot be obtained at one time. You need to traverse two input parameters to obtain the total number of names. Therefore, a Map is used to maintain the parent-child relationship

Note 2

Tree parent-child relationships cannot be compared simply by weight, but by dictionary order of strings, which is determined by the CompareTo method of strings when merging components.

Pay attention to point 3

The final result is to return the total number of names of each tree, and it is easy to search from bottom to top, but tedious to search from top to bottom. Therefore, during the merge operation, the number of names is directly added to the root node, and the total number can be directly obtained.

The problem solving steps

1. Transform and look up the set, and identify the parent-child relationship and the quantity corresponding to the name through two maps. 2. Parse names, initialize names and the number of names in the set. 3. Try to identify and initialize the synonyms in which names are not found. 4. Merge the names with connected relationships. Note that the parent-child relationship should be established according to the dictionary order. 5. Build the result set and return the root node name and the number of names.

Code written

And check set transformation

Class trulyMostPopularUnionFind {/ / because it is a String weight, size and cannot initialize, storage using the map map < String, the String > name2ParentNameMap; Map<String, Integer> name2NameCountMap; Public trulyMostPopularUnionFind () {/ / initializes the component map enclosing name2ParentNameMap = new HashMap < > (); Mmap this.name2NameCountMap = new HashMap<>(); } String find(String name) { if (name2ParentNameMap.get(name).equals(name)) return name; String parentName = find(name2parentNamemap.get (name)); // Path compression String parentName = find(name2parentNamemap.get (name)); name2ParentNameMap.put(name, parentName); return parentName; } void union(String name1, String name2) {// find(name1); String p2 = find(name2); If (p1.equals(p2)) {return (p1.equals(p2)) {return (p1.equals(p2)); 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)); }} int getCount(String name) {parentName = find(name); return name2NameCountMap.get(parentName); } public Map<String, String> getName2ParentNameMap() { return name2ParentNameMap; } public void setName2ParentNameMap(Map<String, String> name2ParentNameMap) { this.name2ParentNameMap = name2ParentNameMap; } public Map<String, Integer> getName2NameCountMap() { return name2NameCountMap; } public void setName2NameCountMap(Map<String, Integer> name2NameCountMap) { this.name2NameCountMap = name2NameCountMap;  }}Copy the code

Algorithmic coding

class Solution { public String[] trulyMostPopular(String[] names, String[] synonyms) { trulyMostPopularUnionFind uf = new trulyMostPopularUnionFind(); List<String> trueNameList = new ArrayList<>(); for (String name : names) { int indexCountStart = name.indexOf('('); int indexCountEnd = name.indexOf(')'); String trueName = name.substring(0, indexCountStart); trueNameList.add(trueName); int count = Integer.valueOf(name.substring(indexCountStart + 1, indexCountEnd)); / / initialization, each component of the parent node to own uf name2ParentNameMap. Put (trueName, trueName); Uf.name2namecountmap. put(trueName, count); } // Merge for (String synonym: synonyms) {String[] twoNames = synonym. Substring (1, synonym.length() - 1).split(","); For (String twoName: twoNames) {if (! uf.name2ParentNameMap.containsKey(twoName)) { uf.name2ParentNameMap.put(twoName, twoName); } if (! uf.name2NameCountMap.containsKey(twoName)) { uf.name2NameCountMap.put(twoName, 0); } } uf.union(twoNames[0], twoNames[1]); } // List<String> res = new ArrayList<>(); For (String trueName: trueNameList) {// Only the root node processes String parentName = uf. Find (trueName); if (trueName.equals(parentName)) { String resString = parentName + "(" + uf.getCount(parentName) + ")"; res.add(resString); } } return res.toArray(new String[res.size()]); }}Copy the code