本文主要是介绍面试题 17.07. 婴儿名字，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
链接：. - 力扣（LeetCode）
题解：
class Solution {
public:vector<string> trulyMostPopular(vector<string>& names, vector<string>& synonyms) {UnionFind uf;for (auto& syn : synonyms) {//cout << "syn:" << syn << endl;auto syn_name = split_name(syn);uf.add(syn_name.first);uf.add(syn_name.second);// 将这两个节点放入一个groupuf.merge(syn_name.first, syn_name.second);}//std::unordered_map<std::string, std::set<People>> fathers;std::unordered_map<std::string, int> fathers_count;// 遍历所有名字for (auto& name : names) {People people;split(name, people);std::string father = uf.get_father(people.name);// 获得父亲，并且按照字典序列进行排序fathers[father].insert(people);//cout << "nnnnn: " << people.name << endl;// 统计按照group父亲节点，总数量fathers_count[father] += people.count;}std::vector<std::string> result;for (auto& father : fathers) {// 获得字典序的第一个名字std::string str = father.second.begin()->name;//cout << "str:" << str << endl;// 获得总数量str = str + "(" + to_string(fathers_count[father.first]) + ")";// 追加结果result.push_back(str);}return result;}
private:
struct People {People() {count = 0;}std::string name;int count = 0;// 按照字典序列进行排序bool operator < (const People& people) const {return name < people.name;}
};void split(string& str, People& people) {auto it = str.find("(");people.name = str.substr(0, it);people.count = atoi(str.substr(it+1, str.size() - it -1).c_str());//cout << "name: " << people.name << " count:" << people.count << endl;}std::pair<std::string, std::string> split_name(string& str) {auto it = str.find(",");std::pair<std::string, std::string> result;result.first = str.substr(1, it-1);result.second = str.substr(it+1, str.size() - it -1);result.second.pop_back();//cout << "first: " << result.first << " second:" << result.second << endl;return result;}
class UnionFind {
public: void add(std::string& p) {auto ite = _father.find(p);if (ite == _father.end()) {_father[p] = p;}}void merge(std::string& p, std::string& q) {std::string p_father = get_father(p);std::string q_father = get_father(q);if (p_father != q_father) {_father[p_father] = q_father;}}std::string get_father(std::string& _p) {add(_p); //如果没有的节点，也要添加个节点std::string p = _p;while (_father[p] != p) {p = _father[p];}return p;}std::unordered_map<std::string, std::string> _father;
};
};这篇关于面试题 17.07. 婴儿名字的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
