Re: [閒聊] 每日leetcode已回收

看板Marginalman作者oin1104 (是oin的說)時間1年前 (2024/07/30 11:31)推噓5(5推 0噓 9→)

留言14則, 5人參與討論串592/1548 (看更多)

之前的那天我用抄的最近練習比較多圖回來再寫一次題目: 有一棵沒有迴圈的樹如果讓你拿一個節點當樹頂讓他的層數最少最矮請問要拿哪些節點思路: 拿最中間那幾個就可以讓他最矮沒有迴圈這點很重要代表可以用拓樸排序整理節點的層數我用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, 1年前 , 1^F

07/30 11:34, 1^F

推

DJYOMIYAHINA

07/30 11:34, 1年前 , 2^F

07/30 11:34, 2^F

→

oin1104

07/30 11:35, 1年前 , 3^F

07/30 11:35, 3^F