一直没好好刷刷 Graph 的题目,从Leetcode graph 套餐 第一个题 310. Minimum Height Trees 开始吧。
题目
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>
保存节点,第一个是节点,第二个是当前的深度。
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
的思路就是 dicuss2
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一个,就是答案了。
这里有两种写法:
第一种就是不断剥离外边那一层,直到剩下最中间的,然后被删掉。
整个树被删光之前,留下的就是我们想要的答案。
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;
}
还有 目前用的郑重
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 创作,最后编辑时间为: May 2, 2019 at 01:37 pm