婴儿名字(Leetcode 程序员面试金典17.07)

发表于 | 分类于 ， ， ， | | 本文总阅读数 次
| 字数统计: 2.1k | 阅读时长 ≈ 9
Leetcode 程序员面试金典17.07

1

题目分析

   这个题目一看就是一个搜索类的题目，其实搜索类的题目我已经拿出来很多了。这个题目又要拿出来说一说，因为它不同于一般的图，一般的图告诉我们邻接矩阵，而这个图类似于朋友圈题目，只告诉我们两两关系，这个题目最直观的方法是并查集，但是如何使用DFS和BFS去求解呢？希望小伙伴们先尝试一下。

DFS

和普通的矩阵图问题不同的是，在地图搜索问题中，往往给定一个起始点，向四个方向搜索即可。但是这个问题没有邻接矩阵，我们要构造一个临界矩阵，找到某个名字和其他名字的关系。

在DFS中，我们建立一个HashMap，其中键为某个名字，值是一个哈希表，其中存放着所有和它相同的名字的集合。

然后建立一个visited集合，存放所有访问过的名字的集合。从第一个名字开始搜索，所有搜索过的名字都加入visited集合，搜完与第一个名字相同的所有名字，并且在搜索过程中取出最小的名字作为真实名字。然后再搜索第二个名字，如果第二个名字和第一个名字是同一个名字，则第二个名字在搜索第一个名字的时候已经加入了visited，继续搜索第三个名字。

算法的**时间复杂度为$O(n + m)$，因为最坏情况下，每个人都和其他所有人名字相同，因此每个键对应的值都是其他所有人的名字，所以空间复杂度为$O(n^2)$**，其中n为名字数量，m为相同名字的关系对数量。

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
#include<iostream>
#include<vector>
#include<unordered_map>
#include<unordered_set>
#include<algorithm>
#include<string>

using namespace std;

class Solution {
public:
    vector<string> trulyMostPopular(vector<string>& names, vector<string>& synonyms) {
        unordered_map<string, int> name;
        for (string s : names) {
            int l = s.find('(');
            int r = s.size() - 1;
            name[s.substr(0, l)] += stoi(s.substr(l + 1, r - l - 1));
        }
        unordered_map<string, unordered_set<string>> relationship;
        for (string s : synonyms) {
            int dot = s.find(',');
            string name1 = s.substr(1, dot - 1), name2 = s.substr(dot + 1, s.size() - dot - 2);
            if (!relationship.count(name1)) { relationship[name1] = unordered_set<string>(); }
            if (!relationship.count(name2)) { relationship[name2] = unordered_set<string>(); }
            relationship[name1].insert(name2);
            relationship[name2].insert(name1);
        }
        unordered_set<string> visited;
        vector<string> res;
        for (auto x : name) {
            if (!visited.count(x.first)) {
                string miniName = x.first;
                int num = dfs(miniName, miniName, name, relationship, visited);
                res.push_back(miniName + "(" + to_string(num) + ")");
            }
        }
        return res;
    }

    int dfs(string curName, string& miniName, unordered_map<string, int>& name, unordered_map<string, unordered_set<string>>& relationship, unordered_set<string>& visited) {
        if (visited.count(curName)) { return 0; }
        visited.insert(curName);
        int res = name[curName];
        for (auto x : relationship[curName]) {
            res += dfs(x, miniName, name, relationship, visited);
            miniName = min(miniName, x);
        }
        return res;
    }
};

BFS

BFS和DFS的预处理过程完全相同，只是我们在搜索时，搜到某个名字，如果某个名字不在visited中，则将其加入visited，说明该名字已经访问过，然后同时将和它相同的所有名字都同时加入到队列中。

这里也不过多赘述，思路也比较简单，多写一些DFS和BFS就会发现它们都是相同的模板。

算法的**时间复杂度为$O(n + m)$，空间复杂度为$O(n^2)$**，其中n为名字数量，m为相同名字的关系对数量。

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
#include<iostream>
#include<vector>
#include<unordered_map>
#include<unordered_set>
#include<algorithm>
#include<string>

using namespace std;

class Solution {
public:
    vector<string> trulyMostPopular(vector<string>& names, vector<string>& synonyms) {
        unordered_map<string, int> name;
        for (string s : names) {
            int l = s.find('(');
            int r = s.size() - 1;
            name[s.substr(0, l)] += stoi(s.substr(l + 1, r - l - 1));
        }
        unordered_map<string, unordered_set<string>> relationship;
        for (string s : synonyms) {
            int dot = s.find(',');
            string name1 = s.substr(1, dot - 1), name2 = s.substr(dot + 1, s.size() - dot - 2);
            if (!relationship.count(name1)) { relationship[name1] = unordered_set<string>(); }
            if (!relationship.count(name2)) { relationship[name2] = unordered_set<string>(); }
            relationship[name1].insert(name2);
            relationship[name2].insert(name1);
        }
        unordered_set<string> visited;
        vector<string> res;
        for (auto x : name) {
            if (!visited.count(x.first)) {
                string miniName = x.first;
                deque<string> queue = { miniName };
                int num = 0;
                while (!queue.empty()) {
                    string curName = queue.front();
                    queue.pop_front();
                    if (visited.count(curName)) { continue; }
                    num += name[curName];
                    visited.insert(curName);
                    for (string neighbor : relationship[curName]) {
                        queue.push_back(neighbor);
                        miniName = min(miniName, neighbor);
                    }
                }
                res.push_back(miniName + "(" + to_string(num) + ")");
            }
        }
        return res;
    }
};

并查集

并查集也是解决这个问题的好方法，虽然并查集没有DFS和BFS那样使用范围大，但是解决朋友圈数量，岛屿个数等等这类问题，最好的方法就是使用并查集。我在数据结构和算法中的算法部分也专门提到过这个方法。

这里再大致说一下，要新建一个并查集UF类，要在类中实现两个最最重要的方法，一个是find，一个是union，在C++语言中不能写union方法，就用merge代替。其中find是找到带头人，merge是合并带头人。什么意思呢？这个问题就是一个合并问题，相同名字合并在一起进行计数。一开始我们让每一个名字的带头人都是自己，数量就是自己的数量。

然后访问合并关系，当两个名字相同时，就让其中一个带头人的带头人是另一个带头人。比如A和B是相同的名字，原本A的带头人是ARoot，ARoot的带头人就是它自己。B的带头人是BRoot，BRoot的带头人也是它自己。我们要合并A和B，就说让ARoot的带头人是BRoot，或者让BRoot的带头人是ARoot，这样我们查找A的带头人和B的带头人都是同一个人。这就相当于合并了A和B。非常类似于生活中的例子，本来有一个校长A，也有一个校长B，那么合并两个学校后，让一个校长变成副校长，听从另一个校长的管理。

在合并时，如果两个带头人不相同，则取较小的那个名字为真正的带头人，并且让较小名字的带头人的数量加上较大名字带头人的数量即可。

最后合并完以后，查看所有的带头人，有多少带头人就有多少个不同的名字，再查看每个名字对应的数字，将其转换为字符串并return即可。

在merge时，对于每一对相同的名字，都要进行find，最坏情况下，每一次find都要向上搜索m次。因此算法的**时间复杂度为$O(n + m^2)$，空间复杂度为$O(n + m)$**，其中n为名字数量，m为相同名字的关系对数量。

因为find的过程非常简单，几乎不用花费很长时间，因此时间消耗和DFS或者BFS几乎差不多。

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
#include<iostream>
#include<vector>
#include<unordered_map>
#include<unordered_set>
#include<algorithm>
#include<string>

using namespace std;

class Solution {
public:
    vector<string> trulyMostPopular(vector<string>& names, vector<string>& synonyms) {
        unordered_map<string, int> name;
        for (string s : names) {
            int l = s.find('(');
            int r = s.size() - 1;
            name[s.substr(0, l)] += stoi(s.substr(l + 1, r - l - 1));
        }
        unordered_map<string, unordered_set<string>> relationship;
        for (string s : synonyms) {
            int dot = s.find(',');
            string name1 = s.substr(1, dot - 1), name2 = s.substr(dot + 1, s.size() - dot - 2);
            if (!relationship.count(name1)) { relationship[name1] = unordered_set<string>(); }
            if (!relationship.count(name2)) { relationship[name2] = unordered_set<string>(); }
            relationship[name1].insert(name2);
            relationship[name2].insert(name1);
        }
        unordered_set<string> visited;
        vector<string> res;
        for (auto x : name) {
            if (!visited.count(x.first)) {
                string miniName = x.first;
                deque<string> queue = { miniName };
                int num = 0;
                while (!queue.empty()) {
                    string curName = queue.front();
                    queue.pop_front();
                    if (visited.count(curName)) { continue; }
                    num += name[curName];
                    visited.insert(curName);
                    for (string neighbor : relationship[curName]) {
                        queue.push_back(neighbor);
                        miniName = min(miniName, neighbor);
                    }
                }
                res.push_back(miniName + "(" + to_string(num) + ")");
            }
        }
        return res;
    }
};

刷题总结

  上面三个方法都需要小伙伴们掌握，能用并查集解决的问题，使用DFS和BFS基本上都可以解决，但是并查集的思想非常好，希望小伙伴能够认真学习。

-------------本文结束感谢您的阅读-------------
0%