wy的leetcode刷题记录_Day60

声明

本文章的所有题目信息都来源于leetcode
如有侵权请联系我删掉!
时间：2022-12-21

前言

这几天身体不舒服，现在重新开始更新。
@TOC

1753. 移除石子的最大得分

今天的每日一题是：1753. 移除石子的最大得分

题目介绍

你正在玩一个单人游戏，面前放置着大小分别为 a、b 和 c 的三堆石子。

每回合你都要从两个不同的非空堆中取出一颗石子，并在得分上加 1 分。当存在两个或更多的空堆时，游戏停止。

给你三个整数 a 、b 和 c ，返回可以得到的最大分数。

示例 1：
输入：a = 2, b = 4, c = 6
输出：6
解释：石子起始状态是 (2, 4, 6) ，最优的一组操作是：
从第一和第三堆取，石子状态现在是 (1, 4, 5)
从第一和第三堆取，石子状态现在是 (0, 4, 4)
从第二和第三堆取，石子状态现在是 (0, 3, 3)
从第二和第三堆取，石子状态现在是 (0, 2, 2)
从第二和第三堆取，石子状态现在是 (0, 1, 1)
从第二和第三堆取，石子状态现在是 (0, 0, 0) 总分：6 分。
示例 2：
输入：a = 4, b = 4, c = 6
输出：7
解释：石子起始状态是 (4, 4, 6) ，最优的一组操作是：
从第一和第二堆取，石子状态现在是 (3, 3, 6)
从第一和第三堆取，石子状态现在是 (2, 3, 5)
从第一和第三堆取，石子状态现在是 (1, 3, 4)
从第一和第三堆取，石子状态现在是 (0, 3, 3)
从第二和第三堆取，石子状态现在是 (0, 2, 2)
从第二和第三堆取，石子状态现在是 (0, 1, 1)
从第二和第三堆取，石子状态现在是 (0, 0, 0) 总分：7 分。

思路

方法一：可以使用模拟法，按照题目所说一点一点减下去得到答案。
方法二：贪心：观察题目后，我们寻找最大值，我们发现当这个最大值大于其他俩个值的和的时候那么，其他俩个值只能与最大值进行分组，所以答案是剩下俩个值的和。如果最大值小于其他俩个值之和，那么其他俩个值不仅需要与最大值组合，剩下的这俩个之间也需要进行组合，最佳的答案就是三个值之和除以2.

代码

class Solution {
public:
    int maximumScore(int a, int b, int c) {
        int max_val=0;
        // max_val=max(a,(b,c));
        max_val=max({a,b,c});
        if(max_val==a)
        {
            if(a>=b+c)
            {
                return b+c;
            }
            else
            {
                return (a+b+c)/2;
            }
        }
        else if(max_val==b)
        {
            if(b>=a+c)
            {
                return a+c;
            }
            else
            {
                return (a+b+c)/2;
            }
        }
        else 
        {
            if(c>=a+b)
            {
                return b+a;
            }
            else
            {
                return (a+b+c)/2;
            }
        }
        
    }
};

收获

观察题目很重要

538. 把二叉搜索树转换为累加树

题目介绍

给出二叉搜索树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

提醒一下，二叉搜索树满足下列约束条件：

节点的左子树仅包含键小于节点键的节点。
节点的右子树仅包含键大于节点键的节点。
左右子树也必须是二叉搜索树。
注意：本题和 1038: https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/ 相同

示例 1：

输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
示例 2：
输入：root = [0,null,1]
输出：[1,null,1]

思路

说实话力扣这个题目描述太笼统了，不太能看清除，