[leetcode] 并查集（Ⅲ）
婴儿名字
题目[Interview-1707]：典型并查集题目。
解题思路
首先对 names 这种傻 X 字符串结构进行预处理，转换为一个 map，key 是名字，val 是名字出现的次数。
然后是把 synonyms 转换为并查集结构，需要注意的是：总是把字典序较小的名字作为连通分量的根。
最后以连通分量的根作为代表，计算每个连通分量的总权重（即每个名字的次数之和）。
代码实现
class Solution
{
public:
unordered_map<string, string> root;
vector<string> trulyMostPopular(vector<string> &names, vector<string> &synonyms)
{
vector<string> ans;
unordered_map<string, int> table;
for (auto &s : names)
{
int idx = s.find('(');
string n = s.substr(0, idx);
int val = stoi(s.substr(idx + 1, s.length() - 2 - idx));
table[n] = val;
}
// build the disjoint-union set
for (auto &str : synonyms)
{
int idx = str.find(',');
string n1 = str.substr(1, idx - 1);
string n2 = str.substr(idx + 1, str.length() - 2 - idx);
merge(n1, n2);
}
// calculate the frequency of root nodes
unordered_map<string, int> mapAns;
for (auto &p : table)
mapAns[find(p.first)] += p.second;
for (auto &p : mapAns)
{
string s = p.first + "(" + to_string(p.second) + ")";
ans.emplace_back(s);
}
return ans;
}
string find(string x)
{
return root.count(x) == 0 ? (x) : (root[x] = find(root[x]));
}
void merge(string x, string y)
{
x = find(x), y = find(y);
if (x < y)
root[y] = x;
else if (x > y)
root[x] = y;
// do nothing if x == y
}
};
冗余连接 Ⅱ
题目[685]：
最新文章
热门文章