阅读量:0
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; } };