310.Minimum Height Trees

一直没好好刷刷 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;
}

作者

mmmwhy

发布于

2018-09-11

更新于

2021-05-30

许可协议