一直没好好刷刷 Graph 的题目，从Leetcode graph 套餐 第一个题 310. Minimum Height Trees 开始吧。
题目
1
2
3
4
5
6
7
8
9
10
11
| Input: n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]
0 1 2
\ | /
3
|
4
|
5
Output: [3, 4]
|
任何一个节点都可以当做root,问那个节点当root的时候，树最低。
基础版BFS
看到题目，第一个想法，就是把所有的节点都当做root跑一遍，看看高度，然后把高度最低的记下来。
使用 pair<int,int> 保存节点，第一个是节点，第二个是当前的深度。
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
| class Solution {
public:
int min_heigh(int n,int now, vector<unordered_set<int>> adj) {
// pair 节点 据定点的距离
pair<int, int > last = {-1,-1};
queue<pair<int,int>> Q;
vector<int> visited(n,0);
Q.push({now,0});
while(!Q.empty()){
pair<int, int> v = Q.front();
visited[v.first] = 1;
Q.pop();
// BFS 用queue
for (int p : adj[v.first]) {
if (visited[p] == 0) {
Q.push({ p,v.second + 1 });
last = { p,v.second + 1 };
}
}
}
return last.second;
}
vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
vector<int> used, min_group;
vector<unordered_set<int>> adj(n);
for (auto p : edges) {
adj[p.first].insert(p.second);
adj[p.second].insert(p.first);
}
int min = INT_MAX;
for (int i = 0; i < n; i++) {
used = {i};
// 第i个点的高度
int temp_i = min_heigh(n,i, adj);
if (temp_i <= min) {
if (temp_i < min) {
min = temp_i;
min_group.clear();
}
min_group.push_back(i);
}
}
return min_group;
}
};
|
本算法大概通过了56/65，然后就超时了….
应该是因为很多节点的高度被重复计算，所以应该换个思路来做。
BFS升级版
dicuss1
dicess2
目测 dicuss1 的思路就是 dicuss2
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
| class Solution {
public:
vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
if (n == 1) {
return{ 0 };
}
vector<int> leaves;
vector<unordered_set<int>> adj(n);
for (pair<int, int> p : edges) {
adj[p.first].insert(p.second);
adj[p.second].insert(p.first);
}
for (int i = 0; i < adj.size(); ++i) {
if (adj[i].size() == 1) {
leaves.push_back(i);
}
}
// BFS the graph
while (n>2) {
n -= leaves.size();
vector<int> newLeaves;
for (int node : leaves) {
for (int neighbor : adj[node]) {
adj[neighbor].erase(node);
if (adj[neighbor].size() == 1)
newLeaves.push_back(neighbor);
}
}
leaves = newLeaves;
}
return leaves;
}
};
|
仔细思考一下这个问题，直观的回答这个问题，找出图中最长的路径，那么这条路径最中间的那一个或者那两个(长度可能是偶数)，就是答案。
但是找最长的路径，其实是一个np问题，很难直接算，第一个算法就尝试直接计算…所以直接超时了..
另外一个思路就是，从叶子开始，一圈一圈的，把最外边那一层的叶子扒掉，最后剩下的2个或者1一个，就是答案了。
这里有两种写法：
第一种就是不断剥离外边那一层，直到剩下最中间的，然后被删掉。
整个树被删光之前，留下的就是我们想要的答案。
1
2
3
4
5
6
7
8
9
10
11
12
13
| while (true) {
vector<int> newLeaves;
for (int node : newLeaves) {
for (int neighbor : adj[node]) {
adj[neighbor].erase(node);
if (adj[neighbor].size() == 1)
leaves.push_back(neighbor);
}
}
if (leaves.empty())
return newLeaves;
newLeaves = leaves;
}
|
还有 目前用的郑重
1
2
3
4
5
6
7
8
9
10
11
12
13
| while (n>2) {
n -= leaves.size();
vector<int> newLeaves;
for (int node : leaves) {
for (int neighbor : adj[node]) {
adj[node].erase(neighbor);
if (adj[neighbor].size() == 1)
newLeaves.push_back(neighbor);
}
}
leaves = newLeaves;
}
|