最长距离

最长路径

https://www.nowcoder.com/questionTerminal/430ded6b482d4d8bbcf2eca6f20e62e3

思路

朴素做法

对每个节点做一次dfs,求出其到其他节点的距离,期间保留最大值即可。

时间复杂度

该做法可通过 的数据

Code

class Solution {
#define pii pair<int, int>
#define ll long
private:
    ll ans;
    vector<pii> g[100010];
public:
    void dfs(int x, int fa, int sum = 0) {
        for (auto cur: g[x]) {
            int v = cur.first, w = cur.second;
            if (v == fa) continue;
            ans = max(sum + w, ans);
            dfs(v, x, sum + w);
        }
    }
    ll solve(int n, vector<int>& u, vector<int>& v, vector<int>& w) {
        // write code here
        for (int i = 0; i < n - 1; ++i) {
            g[u[i]].push_back({v[i], w[i]});
            g[v[i]].push_back({u[i], w[i]});
        }
        for (int i = 1; i <= n; ++i) {
            dfs(i, i, 0);
        }
        return ans;
    }
};

初步优化

对每个叶节点做一次dfs,求出其到其他叶节点的距离,期间保留最大值即可。

最差时间复杂度

该做法可通过 的数据

Code

class Solution {
#define pii pair<int, int>
#define ll long long
private:
    ll ans;
    vector<pii> g[100010];
public:
    void dfs(int x, int fa, ll sum = 0) {
        for (auto cur: g[x]) {
            int v = cur.first, w = cur.second;
            if (v == fa) continue;
            ans = max(sum + w, ans);
            dfs(v, x, sum + w);
        }
    }
    ll solve(int n, vector<int>& u, vector<int>& v, vector<int>& w) {
        // write code here
        for (int i = 0; i < n - 1; ++i) {
            g[u[i]].push_back({v[i], w[i]});
            g[v[i]].push_back({u[i], w[i]});
        }
        for (int i = 1; i <= n; ++i) {
            if (g[i].size() == 1)
                dfs(i, i, 0);
        }
        return ans;
    }
};

标程做法

首先可将该树转化为有根树,考虑为树中的任意两叶节点点的最大距离,不一定经过根节点。
由于是多叉树,最大路径一定是路径和最大的两棵子树的路径和之和。
在dfs过程中可以维护每个结点的两棵最大子树的路径和,保留最大值即可。

时间复杂度

Code

class Solution {
#define pii pair<int, int>
#define maxn 100010
#define ll long long
private:
    int n;
    vector<pii> g[maxn];
    ll f[maxn][2];  //可在dfs过程中用两个变量优化, f[i][0] 表示最大值,f[i][1] 表示次大值
public:
    void dfs(int x, int fa = 0) {
        for (auto cur: g[x]) {
            int v = cur.first, w = cur.second;
            if (v == fa) continue;
            dfs(v, x);
            if (f[x][0] < f[v][0] + w) {
                f[x][1] = f[x][0];
                f[x][0] = f[v][0] + w;
            } else if (f[x][1] < f[v][0] + w){
                f[x][1] = f[v][0] + w;
            }
        }
    }
    ll solve(int n, vector<int>& u, vector<int>& v, vector<int>& w) {
        // write code here
        for (int i = 0; i < n - 1; ++i) {
            g[u[i]].push_back({v[i], w[i]});
            g[v[i]].push_back({u[i], w[i]});
        }
        dfs(1, 0);
        ll res = 0;
        for (int i = 1; i <= n; ++i) {
            res = max(res, f[i][0] + f[i][1]);
        }
        return res;
    }
};
全部评论
感觉第二种也是O(n),无向图,随便哪个点开始dfs,每次都比较,最后也能求到全局最大
点赞 回复 分享
发布于 2021-05-17 16:03

相关推荐

沉淀一会:1.同学你面试评价不错,概率很大,请耐心等待; 2.你的排名比较靠前,不要担心,耐心等待; 3.问题不大,正在审批,不要着急签其他公司,等等我们! 4.预计9月中下旬,安心过节; 5.下周会有结果,请耐心等待下; 6.可能国庆节前后,一有结果我马上通知你; 7.预计10月中旬,再坚持一下; 8.正在走流程,就这两天了; 9.同学,结果我也不知道,你如果查到了也告诉我一声; 10.同学你出线不明朗,建议签其他公司保底! 11.同学你找了哪些公司,我也在找工作。
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务