博客主页 🏗️
wy的leetcode刷题记录_Day60
wy的leetcode刷题记录_Day60

Author:

wy-1226

©

Wordage:

共计 2803 字

needs:

约 2 分钟

Popular:

219 ℃

Created:

目 录

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. 把二叉搜索树转换为累加树

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]

思路

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

代码

收获

文章二维码
wy的leetcode刷题记录_Day60
共计 0 条评论,点此发表评论
博客主页 wyのblog I know you are here. 百度统计
鄂ICP备2023003777号-1 本站已运行 324 天 14 小时 34 分 自豪地使用 Typecho 建站,并搭配 MyDiary 主题 Copyright © 2023 ~ 2024. wyのblog All rights reserved.
打赏图
打赏博主
欢迎
搜 索
足 迹
分 类
  • 默认分类
  • Code
  • 日记
  • 音乐
  • 游戏
  • 阅读
  • 计划
  • 图片
  • 旅游
  • 影视