9.08 华为笔试

第一题

#include <bits/stdc++.h>
using namespace std;

class Tree
{
public:
    Tree(int _val) : val(_val), sum(0), left(nullptr), right(nullptr) {}

    int val;
    int sum;
    Tree* left;
    Tree* right;
};


int main()
{
    int N;
    cin >> N;
    int SumVal = 0;
    vector<Tree*> trees;

    // 记录每个节点的值和整个树的总和
    for (int i = 0; i != N; ++i)
    {
        int temp;
        cin >> temp;
        Tree* newTree = new Tree(temp);
        trees.push_back(newTree);
        SumVal += temp;
    }

    // 记录每个节点的左右子节点
    int jiedian, zijiedian;
    while (cin >> jiedian >> zijiedian)
    {
        if (trees[jiedian]->left == nullptr)
        {
            trees[jiedian]->left = trees[zijiedian];
            continue;
        }
        trees[jiedian]->right = trees[zijiedian];
    }

    // 从尾到头递归决定每个节点的sum值
    for (int i = N - 1; i >= 0; --i)
    {
        Tree* tr = trees[i];
        tr->sum = tr->val;
        if (tr->left == nullptr && tr->right == nullptr)
            continue;
        if (tr->left)
            tr->sum += tr->left->sum;
        if (tr->right)
            tr->sum += tr->right->sum;
    }

    int cha = INT_MIN;
    int biaohao = -1;
    // 计算每个节点差
    for (int i = 0; i != N; ++i)
    {
        int temp = abs(SumVal - trees[i]->sum -trees[i]->sum);
        if (temp > cha)
        {
            cha = temp;
            biaohao = i;
        }
    }

    cout << biaohao << endl;
    return 0;
}

第二题

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int M, N;
    string s;
    cin >> s;
    M = s[0] - '0';
    N = s[2] - '0';

    vector<vector<int>> vec(M, vector<int>(N, 0));
    vector<vector<int>> dp(M, vector<int>(N, 0));

    // 构建vec
    for (int row = 0; row != M; ++row)
    {
        for (int col = 0; col != N; ++col)
        {
            int temp;
            cin >> temp;
            vec[row][col] = temp;
        }
    }

    // 构建dp
    for (int row = 0; row != M; ++row)
    {
        for (int col = 0; col != N; ++col)
        {
            int jump = vec[row][col];
            if (jump == 0) continue;

            // 向下跳跃的dp
            for (int i = row + 1; i != M && i <= row + jump; ++i)
            {
                if (dp[i][col] > dp[row][col] + 1 || dp[i][col] == 0)
                    dp[i][col] = dp[row][col] + 1;
            }

            // 向右跳跃的dp
            for (int j = col + 1; j != N && j <= col + jump; ++j)
            {
                if (dp[row][j] > dp[row][col] + 1 || dp[row][j] == 0)
                    dp[row][j] = dp[row][col] + 1;
            }
        }
    }

    cout << dp[M - 1][N - 1] << endl;

    return 0;
}

第三题

#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;

int main()
{
    string targetMoKuai;
    cin >> targetMoKuai;

    unordered_map<string, int> modules;   // 模块名  时间
    unordered_map<string, vector<string>> yilai;   // 模块名  依赖模块

    string moKuai;
    while (cin >> moKuai)
    {
        int size = moKuai.size();
        int left = 0, right = 0;
        while (moKuai[right] != ',') ++right;

        string newName = moKuai.substr(left, right - left);

        ++right;
        left = right;
        while (right < size && moKuai[right] != ',') ++right;
        int newTime = stoi(moKuai.substr(left, right - left));
        modules[newName] = newTime;

        ++right;
        left = right;
        while (left < size)
        {
            while (right < size && moKuai[right] != ',') ++right;
            string newYiLai = moKuai.substr(left, right - left);

            yilai[newName].push_back(newYiLai);

            ++right;
            left = right;
        }
    }

    // 检查是否有循环依赖


    int totalTime = 0;




    return 0;
}