[路飞]_leetcode-1753-移除石子的最大得分

简介: leetcode-1753-移除石子的最大得分

网络异常,图片无法展示
|


[题目地址][B站地址]


你正在玩一个单人游戏,面前放置着大小分别为 abc三堆 石子。


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


给你三个整数 abc ,返回可以得到的 最大分数


示例 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 分 。
复制代码


示例 3:


输入: a = 1, b = 8, c = 8
输出: 8
解释: 最优的一组操作是连续从第二和第三堆取 8 回合,直到将它们取空。
注意,由于第二和第三堆已经空了,游戏结束,不能继续从第一堆中取石子。
复制代码



提示:


  • 1 <= a, b, c <= 105


解题思路


本题我们不需要求解根据输入数量进行最佳操作的过程,只需要判断输入三个数量之间的一个相互关系即可解题。

  1. 如果最大堆数量之和大于等于于其余两堆之和,那么此时最佳操作就是从最大堆中取出一颗与其余两堆的石子组合,所能得到的最大分数就是较小两堆石子数量之和
  2. 如果最大堆数量之和小于其余两堆之和,那么此时通过合理操作,最后最多只会剩下一个石子(即三堆数量之和为奇数的情况),所以此时最大分数等于三堆数量之和 sum/2 向下取整


代码实现


var maximumScore = function(a, b, c) {
  // 获取较小两堆的和值
  const arr = [a,b,c]
  arr.sort((a,b) => a-b)
  const sum = arr[0]+arr[1]
  // 判断较小两堆和值是否小于最大堆数量
  if(sum<=arr[2]){
    // 如果最大堆数量大于其余两堆数量,最大分数为其余两堆数量之和
    return sum;
  }else{
    // 否则为石子总数除以2向下取整
    return (sum+arr[2])>>1
  }
};
复制代码


至此我们就完成了 leetcode-1753-移除石子的最大得分


如有任何问题或建议,欢迎留言讨论!

相关文章
LeetCode-798 得分最高的最小论调 及差分和前缀和的学习
LeetCode-798 得分最高的最小论调 及差分和前缀和的学习
|
6月前
|
机器学习/深度学习 算法 测试技术
【单调栈】LeetCode:2818操作使得分最大
【单调栈】LeetCode:2818操作使得分最大
|
6月前
|
算法 测试技术 C#
【二分查找】【双指针】LeetCode:2565最少得分子序列
【二分查找】【双指针】LeetCode:2565最少得分子序列
|
6月前
leetcode-2029.:石子游戏 IX
leetcode-2029.:石子游戏 IX
39 0
|
6月前
|
算法 测试技术 C++
【二分查找】【双指针】LeetCode:2565最少得分子序列
【二分查找】【双指针】LeetCode:2565最少得分子序列
|
人工智能 算法 C语言
LeetCode.每日一题 1039. 多边形三角剖分的最低得分
这题是一道区间Dp问题,将一个多边形形划分为若干个三角形,求其最小的得分.
97 0
|
算法 C++
【每日算法Day 64】LeetCode 861. 翻转矩阵后的得分
【每日算法Day 64】LeetCode 861. 翻转矩阵后的得分
|
人工智能 算法 C++
每日算法系列【LeetCode 1039】多边形三角剖分的最低得分
每日算法系列【LeetCode 1039】多边形三角剖分的最低得分
103 0
|
前端开发 JavaScript 算法
LeetCode分割字符串的最大得分使用JavaScript解题,击败了100%的用户|前端学算法
LeetCode分割字符串的最大得分使用JavaScript解题,击败了100%的用户|前端学算法
104 0
LeetCode分割字符串的最大得分使用JavaScript解题,击败了100%的用户|前端学算法