据说做全对也进不了面试记录一下吧代码啥的
还挺有意思
无所谓！
这次甚至出现了提前批出现过的原题，第三题背包，显然就是不想找人吧哈哈笑死！

1.删二叉树
题意：给定一个二叉树，删除尽可能少的节点，使得二叉树变为满二叉树！
思路：bfs的逐层拓展，按照满二叉树来算，那么每一层是上一层点数的两倍，所以逐层判断，当有一层不满时从这一层开始的每一层的节点都是要删除的。但是层数可能有1e5，所以要用一变量记录什么时候会不足。2的1e5次方肯定是会爆int的。

int num0fNode(TreeNode *root)
{
    queue<TreeNode*>qu;
    qu.push(root);
    int sum=0,k=1;//k表示计算当前层应该有多少个节点。
    bool tp=true;
    while(qu.size())
    {
        int n=qu.size();
        if(n!=k) tp=false;
        if(!tp) sum+=n;
        k*=2;
        while(n--)
        {
            auto p=qu.front();
            qu.pop();
            if(p->left!=NULL) qu.push(p->left);
            if(p->right!=NULL) qu.push(p->right);
        }
    }
    return sum;

}

2.作弊风险？这个题竟然是上次提前批bishi题目，一个字没改哈哈

题目：把一个比赛抽象成an，bn，cn，如果你牛逼，你会得到ai的变化，如果你zuobi，bi改变，ci表示作弊风险
初始分数是1500，作弊风险不能超过k

解法：动态规划，对于每一个物品只会选择两者中的一个也就是分组背包。
dp[i][j]，代表取了i个物品，当前作弊值达到了j。
主要函数为：
第一层循环枚举i，第二层循环的第一个是假设不作弊推出所有的dp值，第二层循环的第二个是假设作弊那么就可以更新dp值，不过只能用不足当前c[i]的dp值来更新。

#include<bits/stdc++.h>
using namespace std;
int n,m; //n数组大小，m是风险上限
int a[1005],b[1005],c[1005];
long long dp[1005][1005];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    for(int i=1;i<=n;i++) cin>>c[i];

    dp[0][0]=1500;

    for(int i=1;i<=n;i++){
        for(int j=0;j<=m;j++){
            dp[i][j]=dp[i-1][j]+a[i];
        }
        for(int j=c[i];j<=m;j++){
            dp[i][j]=max(dp[i][j],dp[i-1][j-c[i]]+b[i]);
        }
    }

    long long res=0;
    for(int i=0;i<=m;i++){
        res=max(res,dp[n][i]);
    }
    cout<<res<<endl;

    return 0;
}

例子：
5 10
1 -1 1 -1 1
100 10 100 10 100
4 4 4 4 4

1699

3.二叉数的最大权值路径

这个题力扣124题
这个题目可以说是hard题，而且考频次很高

先贴下原题代码

class Solution {
public:
    int dfs(TreeNode* root, int &res)
    {
        if (root == nullptr) return 0;
        int left = max(0, dfs(root->left, res));
        int right = max(0, dfs(root->right, res));

        //取最大值时取两边，因为路径可以从左叶子节点走到右叶子节点
        res = max(res, root->val + left + right);   
        return root->val + max(left, right);        //返回时只能返回较大的一边
    }

    int maxPathSum(TreeNode* root) {
        int res = -1000;
        if (root == nullptr) return 0;

        dfs(root, res);
        return res;
    }
};

看到这题无脑歇过来发现没有ac
原因是这个题目路径是从上到下的
就是res更新需要明确要更新的事根节点的值加上左右两边的那个较大的值
和递归一样
只能走一编

因此改为

class Solution {
public:
    int dfs(TreeNode* root, int &res)
    {
        if (root == nullptr) return 0;
        int left = max(0, dfs(root->left, res));
        int right = max(0, dfs(root->right, res));

        //取最大值时无法取两边
        res = max(res, max(root->val,root->val+max(left,right)));   //*******jike
        return root->val + max(left, right);        //返回时只能返回较大的一边
    }

    int maxPathSum(TreeNode* root) {
        int res = -1000;
        if (root == nullptr) return 0;

        dfs(root, res);
        return res;
    }
};