307 week contest

这里介绍3，4题

当天并没有参加周赛

这是今天突然想做，1,2题能够很好的ac

但是第三题和第四题总是存在些问题，就是简单记录一下我的思路，主要是错误答案和标准答案的思路。

 当时的思路是计算三个高度

d1: 被感染节点的高度

d：以被感染节点为根的树的高度

depth：将感染节点的孩子的孩子均置为空 计算高度

最终返回  max（depth+d1,d）

反正整个算的就很麻烦，我感觉我的思路是ok的但是实现可能是出现问题，但还是卡了数据。

看了官方题解，再看我写真的太蠢了

其实本质上就是从感染点开始的路径问题

利用一次dfs进行后续遍历

增加一个参数记录感染的时间

如果是根节点感染，那么子孩子感染时间加一

如果是左子树的根节点感染 返回她感染时间然后加一 感染右子树节点

class Solution {
public:
    int max=0;
    int  dfs(TreeNode* root, int start,int sum){
        if(root==NULL)return -1;
        if(sum==-1&&root->val==start){//本节点为感染节点
            sum=0;
        }
        if(sum!=-1){//本节点已感染，传递到子树中
            dfs(root->left,start,sum+1);
            dfs(root->right,start,sum+1);
            if(sum>max)max=sum;
            return sum+1;
        }else{
            int tem=dfs(root->left,start,sum);
            if(tem!=-1){//左子树被感染，传递到右子树
                sum=tem;
                dfs(root->right,start,sum+1);
            }else{//右子树被感染，传递到左子树
                sum=dfs(root->right,start,sum);
                dfs(root->left,start,sum+1);
            }
        }
        if(sum>max)max=sum;
        if(sum!=-1)return sum+1;
        return -1;
    }
    int amountOfTime(TreeNode* root, int start) {
        dfs(root,start,-1);
        return max;
    }
};

当时想的是按照二进制进行计算，将正数负数区分开，利用二进制对其排序得到第k大序列

测试的时候发现自己想简单了，单独的正数或负数这种方法没有问题，但是在整数范围内无法用二进制数来判断序列的大小。

官方题解利用堆来进行求解

最大序列为所有正数相加。

两个操作：

• 保留 nums[i-1]
• 不保留 nums[i-1]，增加之前减去的

这两个操作可以认为是0，1 操作，可以确保所有序列都可以遍历到

利用堆的排序特性，选出最大值，不断弹出

class Solution {
public:
    long long kSum(vector<int> &nums, int k) {
        long sum = 0L;
        for (int &x : nums)
            if (x >= 0) sum += x;
            else x = -x;
        sort(nums.begin(), nums.end());
        priority_queuelong, int>> pq;
        pq.emplace(sum, 0);
        while (--k) {
            auto[sum, i] = pq.top();
            pq.pop();
            if (i < nums.size()) {
                pq.emplace(sum - nums[i], i + 1); // 保留 nums[i-1]
                if (i) pq.emplace(sum - nums[i] + nums[i - 1], i + 1); // 不保留 nums[i-1]，把之前减去的加回来
            }
        }
        return pq.top().first;
    }
};