Re: [閒聊] 每日leetcode

[sixB (6B)]

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

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.205.121.194 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1735074183.A.E00.html
推 Meaverzt: 大師