蔚来笔试DC图形20220824（AK）

第一题：二叉树删除最少结点实现满二叉树

class Solution {
public:
    int helper(TreeNode *root) {
        queue<TreeNode *> myque;
        int floor = 1;
        myque.push(root);
        int sum = 0;
        while (!myque.empty()) {
            int sz = myque.size();
            if (sz != pow(2, floor - 1)) {
                sum += sz;
            }
            for (int i = 0; i < sz; ++i) {
                TreeNode *node = myque.front();
                myque.pop();
                if (node->left) myque.push(node->left);
                if (node->right) myque.push(node->right);
            }
            floor++;
        }
        return sum;
    }

    int numOfNode(TreeNode *root) {
        if (root == nullptr) {
            return 0;
        }
        return helper(root);
    }
};

第二题：二叉树最大权值和

class Solution {
    int maxVal = INT32_MIN;
    void dfs(TreeNode *root, int path) {
        if (root == nullptr) return;
        path += root->val;
        maxVal = max(maxVal, path);
        dfs(root->left, path);
        dfs(root->right, path);
        path -= root->val;
    }
    void helper(TreeNode *root) {
        if (root == nullptr) return;
        dfs(root, 0);
        helper(root->left);
        helper(root->right);
    }

public:
    int maxSum(TreeNode *root) {
        // write code here
        helper(root);
        return maxVal;
    }
};

第三题：科学上分，“倡导高效作弊”，哈哈哈哈

#include <math.h>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    // 输入数据处理
    int n, k;
    cin >> n >> k;
    vector<int> aNums(n, 0);
    for (int i = 0; i < n; ++i) {
        cin >> aNums[i];
    }
    vector<int> bNums(n, 0);
    for (int i = 0; i < n; ++i) {
        cin >> bNums[i];
    }
    vector<int> cNums(n, 0);
    for (int i = 0; i < n; ++i) {
        cin >> cNums[i];
    }
    // 解题
    // 计算作弊带来的收益
    vector<int> benefits(n, 0);
    for (int i = 0; i < n; ++i) {
        benefits[i] = bNums[i] - aNums[i];
    }
    // 转换为dp问题
    long long score = 0;
    for (int n : aNums) {
        score += n;
    }
    if (k == 0) {
        cout << 1500 + score << endl;
    } else {
        vector<long long> dp(k + 1, 0);
        for (int i = 0; i < n; ++i) {
            for (int j = k; j >= cNums[i]; --j) {
                dp[j] = max(dp[j], dp[j - cNums[i]] + benefits[i]);
            }
        }
        cout << 1500 + dp.back() + score << endl;
    }
}

总结：题目都不难，对时间复杂度的要求不高，最后一题稍微要转个弯弯，用DP的方法（01背包问题）找最佳的作弊方法