当前位置：网站首页>【小码匠自习室】叛逆的小孩，打死也不改

【小码匠自习室】叛逆的小孩，打死也不改

2022-08-08 13:52:00 【小码匠】

对话

小码匠：这道题我的代码量最小，一次AC。

老码农：我看看，你，你，你的代码宇宙无敌第一简单。

小码匠：我厉害吧。

老码农：你厉害，俺服了你了。

小码匠：怎么听着味道不对啊？

老码农：同一道题比上次（1个月之前）功力大增，执行之间缩短了一半多，内存消耗也小了，可你怎么就这么不听话呢。。。

小码匠：是你老跟我说，要遵从自己内心的想法，小孩也要有主见。。。骗人的鬼话。。。

老码农：小码匠，咱们在学习图搜索，你用递归去写，好不好啊。。。

小码匠：不好，我的题解在所有C++解法中排第二位、内存消耗量比第一小20%，已经很接近完美了。

老码农：那是，你是谁，神勇无敌小码匠，擅用多种解法解决问题，递归搜索算个啥，对小码匠来说不在话下。。。

小码匠：行啦，硬的不行来甜言蜜语，我再尝试用递归搞搞，非得逼着我用递归，我讨厌递归、递归。。。

题目地址

Q4. 木の高さ
- https://algo-method.com/tasks/528

問題描述

乌龟阿尔勒有顶点数N的树。树的顶点有从0到N-1的编号。根是0顶点。

另外，顶点i的父顶点P（1≤i≤N-1）。

求阿尔勒所拥有的树的高度。

但是，树的高度是指“到达根最远的顶点之前需要到达的边的数量”。

输入

输入的格式如下：

N P P P

约束条件

输入的值满足下面条件

N大于等于2小于等于10000的整数
P_i 大于等于0小于等于 i−1的整数 (1≤i≤N−1)

输出

输出结果

输入示例 1

7
0 1 0 0 1 5

输入示例 1

如下图，离顶点0最远的顶点是6，从根到顶点6经过的边数：4，所以树高是3。

输入示例 2

7
0 0 0 0 0 0

输出示例 2

小码匠题解

void best_solution() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n ;
    vector<int> a(n);
    int b;
    int ans = 0;
    for(int i = 1; i < n; ++i) {
        cin >> b;
        a[i] = a[b] + 1;
        ans = max(a[i], ans);
    }
    cout << ans;
}

小码匠题解（DFS）

哼、哼、哼，讨厌的递归

代码量: 翻了一倍
执行时间：长了3毫秒
内存消耗：长了15%

void dfs(int i, const vector<vector<int>> &vi, vector<int> &dfs_list) {
    if (i == 0) {
        dfs_list[i] = 0;
    }
    for (auto a: vi[i]) {
        dfs_list[a] = dfs_list[i] + 1;
        dfs(a, vi, dfs_list);
    }
}

void coder_solution() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n ;
    vector<int> a(n);
    int temp;
    vector<vector<int>> vi(n);
    for (int i = 1; i < n; ++i) {
        cin >> temp;
        vi[temp].push_back(i);
    }
    dfs(0, vi, a);
    int ans = 0;
    for(auto i : a) {
        ans = max(i, ans);
    }
    cout << ans;
}

小码匠题解（5月份）

执行耗时：35ms
内存消耗：4112KB

void coder_solution() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    map<int, int> mii;
    mii[0] = 0;
    int temp;
    int max_num = 0;
    for(int i = 1; i < n; i++) {
        cin >> temp;
        mii[i] = mii[temp] + 1;
        max_num = max(max_num, mii[i]);
    }
    cout << max_num;
}

原网站

版权声明
本文为[小码匠]所创，转载请带上原文链接，感谢
https://cloud.tencent.com/developer/article/2068168