作者DJYOSHITAKA (franchouchouISBEST)
看板Marginalman
標題Re: [閒聊] 每日LeetCode
時間Fri Feb 23 00:53:44 2024
1245. Tree Diameter
premium題 找出一個tree的最長path
看起來不太直覺 其實只是實作一個找depth的function
同時記下前兩深的subtree的深度 同時更新最長path長度
最長path必會是某個root的兩個最深subtree的深度相加再+2
DFS的過程就可以順便更新
寫起來不難 但不熟的話一開始會卡:( 希望有記起來
class Solution {
public:
int helper(unordered_map<int, vector<int>>& g, int root, int parent, int*
ans)
{
// calculate depth
int max_depth_1 = -1, max_depth_2 = -1;
for(auto n : g[root])
{
if(n != parent)
{
max_depth_2 = max(max_depth_2, helper(g, n, root, ans));
if(max_depth_2 > max_depth_1) swap(max_depth_1, max_depth_2);
}
}
// update ans
*ans = max(*ans, max_depth_1+max_depth_2+2);
// return depth
return max_depth_1+1;
}
int treeDiameter(vector<vector<int>>& edges) {
unordered_map<int, vector<int>> g;
for(auto e : edges)
{
g[e[0]].push_back(e[1]);
g[e[1]].push_back(e[0]);
}
int ans = 0;
int depth = helper(g, 0, -1, &ans);
return ans;
}
};
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.137.183.60 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1708620827.A.D70.html
→ wu10200512: 你的每日怎麼跟我不一樣 02/23 00:55
→ DJYOSHITAKA: 課金題 對ㄚ== 02/23 00:56
→ DJYOSHITAKA: 每周課金題 02/23 00:56
推 pandix: 大師 02/23 00:57
→ wu10200512: 課金題是三小 題庫裡沒有的喔 02/23 00:57
→ DJYOSHITAKA: 要買premium 可以等特價 02/23 00:59
推 NCKUEECS: 大師 02/23 01:03
→ JIWP: 大師 02/23 01:09
→ JerryChungYC: 看到這篇才想到之前寫的程式鎖住的題目也能抓到 02/23 01:21
→ JerryChungYC: 不過不能在leetcode上送出也沒甚麼用就是了 02/23 01:21
→ DJYOSHITAKA: 大師:OOO 02/23 01:25