Re: [閒聊] 每日leetcode

看板Marginalman作者sixB (6B)時間11月前 (2024/12/25 05:03)推噓1(1推 0噓 0→)

3203. 好久沒有遇到解這麼順的hard了好感動qwq 順順寫完只有被原本樹最長的小坑一下很快修掉就過了看起來跟大家寫的一樣差在set好慢然後max弄成陣列去比也好慢 class Solution { public: int minimumDiameterAfterMerge(vector<vector<int>>& edges1, vector<vector<int>>& edges2) { // (dia1 + 1) / 2 + (dia2 + 1) / 2 + 1 int n = edges1.size() + 1, m = edges2.size() + 1; vector<vector<int>> adj1(n), adj2(m); for(auto& e: edges1){ adj1[e[0]].push_back(e[1]); adj1[e[1]].push_back(e[0]); } for(auto& e: edges2){ adj2[e[0]].push_back(e[1]); adj2[e[1]].push_back(e[0]); } int dia1 = 0, dia2 = 0; unordered_set<int> seen1, seen2; set_dia(0, adj1, dia1, seen1); set_dia(0, adj2, dia2, seen2); cout << dia1 << " " << dia2; return max({dia1, dia2, ((dia1 + 1) / 2 + (dia2 + 1) / 2 + 1)}); } int set_dia(int idx, vector<vector<int>>& adj, int& dia, unordered_set<int>& seen){ if(seen.count(idx)) return -1; seen.insert(idx); int mx1 = 0, mx2 = 0; for(auto& i: adj[idx]){ int dep = set_dia(i, adj, dia, seen) + 1; if(dep > mx1){ mx2 = mx1; mx1 = dep; } else mx2 = max(mx2, dep); dia = max({dia, mx1 + mx2, dep}); } return mx1; } }; ----- Sent from JPTT on my iPad -- 很姆的咪姆之咪 http://i.imgur.com/5sw7QOj.jpg