2024.7.19 刷题总结

2024.7.19

**每日一题**

3096.得到更多分数的最少关卡数目，这道题是一个考察前缀和的题目，根据题意我们需要先把数组的0转为-1，然后计算两个部分的数组和，所以我们可以现预处理出前缀和数组，然后枚举每个点作为切分点，除了最后一个点，然后判断是否符合条件，否则输出-1.

class Solution {
public:
    int minimumLevels(vector<int>& possible) {
        int n = possible.size();
        for(int i =0;i<n;i++){
            if(possible[i]==0) possible[i]=-1;
        }
        vector<int> sum(n,0);
        sum[0]=possible[0];
        for(int i =1;i<n;i++){
            sum[i]=sum[i-1]+possible[i];
        }
        for(int i =0;i<n;i++){
            if((i<n-1)&&(sum[i]>sum[n-1]-sum[i])){
                return i+1;
            }
        }
        return -1;
    }
};

124.二叉树中的最大路径和，这是一道考察递归的题目，从根节点出发，类似于dfs，分别递归寻找左右节点的路径和，直到叶子节点再返回，从叶子节点往上更新以每个节点为根节点的最大路径，直到返回根节点，用一个变量来维护答案.

class Solution {
public:
    int ans = -10000000;
    int getSum(TreeNode* root){
        if(root==nullptr) return 0;
        int leftSum = max(getSum(root->left),0);
        int rightSum = max(getSum(root->right),0);
        int cnt = root->val+leftSum+rightSum;
        ans = max(ans,cnt);
        return root->val+max(leftSum,rightSum);
    }
 
    int maxPathSum(TreeNode* root) {
         int a = getSum(root);
         return ans;
    }
};

543.二叉树的直径，这道题是一道考察递归的题目，按照树的一般算法，维护一个最大直径答案值，定义一个递归函数，开头是递归返回条件，即当前节点为空节点就返回0，否则分别往左和往右递归，维护每个节点的最大深度为左右最大深度中的最大值再加一，答案用左右节点的最大深度的和再加一来维护.

class Solution {
public:
    int ans;
    int depth(TreeNode* root){
        if(root==nullptr) return 0;
        int L=depth(root->left);
        int R=depth(root->right);
        ans=max(ans,L+R+1);
        return max(L,R)+1;
    }
    int diameterOfBinaryTree(TreeNode* root) {
        ans = 1;
        depth(root);
        return ans-1;   
 
    }
};