作者oin1104 (是oin的說)
看板Marginalman
標題Re: [閒聊] 每日leetcode
時間Tue Jul 30 11:31:26 2024
之前的
那天我用抄的
最近練習比較多圖
回來再寫一次
題目:
有一棵沒有迴圈的樹
如果讓你拿一個節點當樹頂
讓他的層數最少 最矮
請問要拿哪些節點
思路:
拿最中間那幾個
就可以讓他最矮
沒有迴圈這點很重要
代表可以用拓樸排序整理節點的層數
我用khan的方法來找出大家的層數
從外圈bfs到內圈
然後找出最中間的那幾個
```cpp
class Solution {
public:
vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges)
{
if(n == 1)return {0};
if(n == 2)return {0,1};
int len = edges.size();
vector<int> one(n,-1);
vector<int> visited(n,0);
unordered_map<int,vector<int>> save;
vector<int> layer(n,0);
for(int i = 0; i < n-1 ; i ++)
{
one[edges[i][0]]++;
one[edges[i][1]]++;
save[edges[i][0]].push_back(edges[i][1]);
save[edges[i][1]].push_back(edges[i][0]);
}
queue<pair<int,int>> paper;
for(int i = 0 ; i < n ; i ++)
{
if(one[i] == 0)
{
visited[i] = 1;
paper.push({i,1});
}
}
while(!paper.empty())
{
pair<int,int> k = paper.front();
paper.pop();
layer[k.first] = k.second;
for(int go : save[k.first])
{
one[go]--;
if(one[go] == 0)
{
//cout << "my go !!!!!";
paper.push({go,k.second+1});
}
}
}
vector<int> res;
int k = 0;
for(int i = 0 ; i < n ; i ++)
{
//cout<<layer[i]<<" ";
k = max(k,layer[i]);
}
for(int i = 0 ; i < n ; i ++)
{
if(layer[i] == k)res.push_back(i);
}
return res;
}
};
```
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.12.27.25 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1722310288.A.80E.html
推 JIWP: 你怎麼用抄的,我對你很失望,不崇拜你了 07/30 11:34
推 DJYOMIYAHINA: 這好久以前了 我好崇拜你 07/30 11:34
→ oin1104: 阿就不會寫 07/30 11:35
→ sustainer123: 大師 07/30 11:36
推 Chricey: 馬卡 07/30 11:36 → JIWP: 這哪題? 07/30 11:37
→ SydLrio: 你有什麼用 07/30 11:37
→ oin1104: min height tree 07/30 11:38
推 Chricey: uc2推薦 07/30 11:38 → oin1104: 你翻之前每日就有 07/30 11:38
推 JIWP: 我對你很失望,你模型沒了 07/30 11:39
→ oin1104: 所以我現在不是寫了嗎 在哭喔 07/30 11:40
推 Chricey: 鋅的作用 07/30 11:40 推 JIWP: 這題不就撥洋蔥 07/30 11:41
→ JIWP: 從最外層一直剝 07/30 11:41
→ oin1104: 阿那時候不知道拓樸 07/30 11:42
推 Chricey: 甘草功效 07/30 11:42 推 JIWP: 我也不知道,對啊 07/30 11:43