Re: [閒聊] 每日LeetCode
看板Marginalman作者DJYOSHITAKA (franchouchouISBEST)時間3月前 (2024/02/23 00:53)推噓3(3推 0噓 9→)留言12則, 6人參與討論串709/719 (看更多)
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
→
02/23 00:55,
3月前
, 1F
02/23 00:55, 1F
→
02/23 00:56,
3月前
, 2F
02/23 00:56, 2F
→
02/23 00:56,
3月前
, 3F
02/23 00:56, 3F
推
02/23 00:57,
3月前
, 4F
02/23 00:57, 4F
→
02/23 00:57,
3月前
, 5F
02/23 00:57, 5F
→
02/23 00:59,
3月前
, 6F
02/23 00:59, 6F
推
02/23 01:03,
3月前
, 7F
02/23 01:03, 7F
→
02/23 01:09,
3月前
, 8F
02/23 01:09, 8F
推
02/23 01:21,
3月前
, 9F
02/23 01:21, 9F
→
02/23 01:21,
3月前
, 10F
02/23 01:21, 10F
→
02/23 01:21,
3月前
, 11F
02/23 01:21, 11F
→
02/23 01:25,
3月前
, 12F
02/23 01:25, 12F
討論串 (同標題文章)
完整討論串 (本文為第 709 之 719 篇)：
閒聊
1
3