蔚来笔试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背包问题)找最佳的作弊方法

#蔚来##蔚来笔试#
全部评论
感觉二叉树被考到的几率好大啊
点赞 回复 分享
发布于 2022-08-27 22:55 陕西

相关推荐

07-25 11:12
重庆大学 C++
既然这么缺人,为什么挂我呢
希望被offer砸中...:其实不缺人
点赞 评论 收藏
分享
07-11 22:27
中南大学 Java
程序员牛肉:学历的话没问题。但是没问题的也就只有学历了。 其实你的整体架构是正确的,博客接着干。但是项目有点过于简单了。从后端的角度上讲,你这也就是刚入门的水平,所以肯定约面试够呛。 如果你要应聘后端岗位,那你第一个项目竟然是仿写操作系统。这个你要面试官咋问你。你一定要记住一点,你简历上写的所有的东西,都是为了证明你有能力胜任当前的岗位,而不是为了证明你自己会什么。 如果你只是浅浅的做几个项目,描述也都是烂大街。技术点也都是各种混水类的配置类需求,那你就不要幻想自己能走多远。一定要保持思考,保持学习。
点赞 评论 收藏
分享
认真搞学习:这么良心的老板真少见
点赞 评论 收藏
分享
评论
1
6
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务