拿出最少数目的魔法豆

2024-01-19 00:12
文章标签 魔法 少数 目的 拿出

本文主要是介绍拿出最少数目的魔法豆,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

说在前面

🎈不知道大家对于算法的学习是一个怎样的心态呢?为了面试还是因为兴趣?不管是出于什么原因,算法学习需要持续保持。

题目描述

请你从每个袋子中 拿出 一些豆子(也可以 不拿出),使得剩下的 非空 袋子中(即 至少还有一颗 魔法豆的袋子)魔法豆的数目 相等。一旦把魔法豆从袋子中取出,你不能再将它放到任何袋子中。

请返回你需要拿出魔法豆的 最少数目。

示例 1:

输入:beans = [4,1,6,5]
输出:4
解释:
- 我们从有 1 个魔法豆的袋子中拿出 1 颗魔法豆。剩下袋子中魔法豆的数目为:[4,0,6,5]
- 然后我们从有 6 个魔法豆的袋子中拿出 2 个魔法豆。剩下袋子中魔法豆的数目为:[4,0,4,5]
- 然后我们从有 5 个魔法豆的袋子中拿出 1 个魔法豆。剩下袋子中魔法豆的数目为:[4,0,4,4]
总共拿出了 1 + 2 + 1 = 4 个魔法豆,剩下非空袋子中魔法豆的数目相等。
没有比取出 4 个魔法豆更少的方案。

示例 2:

输入:beans = [2,10,3,2]
输出:7
解释:
- 我们从有 2 个魔法豆的其中一个袋子中拿出 2 个魔法豆。剩下袋子中魔法豆的数目为:[0,10,3,2]
- 然后我们从另一个有 2 个魔法豆的袋子中拿出 2 个魔法豆。剩下袋子中魔法豆的数目为:[0,10,3,0]
- 然后我们从有 3 个魔法豆的袋子中拿出 3 个魔法豆。剩下袋子中魔法豆的数目为:[0,10,0,0]
总共拿出了 2 + 2 + 3 = 7 个魔法豆,剩下非空袋子中魔法豆的数目相等。
没有比取出 7 个魔法豆更少的方案。

提示:

  • 1 <= beans.length <= 105
  • 1 <= beans[i] <= 105

解题思路

这道题我们比较容易看出其实就是一道前缀和的题目,我们可以分为以下几步来进行解题,这里我们以示例一为例子来详说解题步骤:

对数组进行排序

我们可以先对数组进行排序

beans.sort((a, b) => b - a);

排序后的数组如下:

计算每个下标前面的元素置为当前元素值所需要减去的总和

[6] => [6] = 6 - 6 = 0
[6,5] => [5,5] = (6 - 5) + (5 - 5) = 1
[6,5,4] => [4,4,4] = (6 - 4) + (5 - 4) + (4 - 4) = 3
[6,5,4,1] => [1,1,1,1] = (6 - 1) + (5 - 1) + (4 - 1) + (1 - 1) = 12

从后往前计算前缀和

遍历每种取法,找出最小的取法

从上图我们可以看出前三项置为4,最后一下置为0是最优的取法。

AC代码

/*** @param {number[]} beans* @return {number}*/
var minimumRemoval = function (beans) {beans.sort((a, b) => b - a);const cnt = new Array(beans.length).fill(0);for (let i = 1; i < beans.length; i++) {cnt[i] = (beans[i - 1] - beans[i]) * i + cnt[i - 1];}let min = cnt[cnt.length - 1];let sum = 0;for (let i = beans.length - 1; i > 0; i--) {sum += beans[i];min = Math.min(sum + cnt[i - 1], min);}return min;
};

公众号

关注公众号『前端也能这么有趣』,获取更多有趣内容。

说在后面

🎉 这里是 JYeontu,现在是一名前端工程师,有空会刷刷算法题,平时喜欢打羽毛球 🏸 ,平时也喜欢写些东西,既为自己记录 📋,也希望可以对大家有那么一丢丢的帮助,写的不好望多多谅解 🙇,写错的地方望指出,定会认真改进 😊,偶尔也会在自己的公众号『前端也能这么有趣』发一些比较有趣的文章,有兴趣的也可以关注下。在此谢谢大家的支持,我们下文再见 🙌。

这篇关于拿出最少数目的魔法豆的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/620714

相关文章

2024 年高教社杯全国大学生数学建模竞赛题目——2024 年高教社杯全国大学生数学建模竞赛题目的求解

2024 年高教社杯全国大学生数学建模竞赛题目 (请先阅读“ 全国大学生数学建模竞赛论文格式规范 ”) 2024 年高教社杯全国大学生数学建模竞赛题目 随着城市化进程的加快、机动车的快速普及, 以及人们活动范围的不断扩大,城市道 路交通拥堵问题日渐严重,即使在一些非中心城市,道路交通拥堵问题也成为影响地方经 济发展和百姓幸福感的一个“痛点”,是相关部门的棘手难题之一。 考虑一个拥有知名景区

探索Python的数学魔法:Numpy库的神秘力量

文章目录 探索Python的数学魔法:Numpy库的神秘力量背景:为什么选择Numpy?Numpy是什么?如何安装Numpy?五个简单的库函数使用方法场景应用常见Bug及解决方案总结 探索Python的数学魔法:Numpy库的神秘力量 背景:为什么选择Numpy? 在Python的世界中,数据处理和科学计算是不可或缺的一部分。但原生Python在处理大规模数据时可能会显

玩转Python Turtle库,实现满屏飘字的魔法!

前言     本文将教你如何使用Python的Turtle库,通过简单的编程实现满屏飘字的炫酷效果。无需复杂的编程知识,跟着我们的步骤,你也可以成为编程小达人! 效果展示 开发过程 一、准备工作 首先,确保你的电脑上已经安装了Python环境。然后,你需要安装或更新Turtle库(通常Python安装时自带了Turtle库)。 二、编写代码 接下来,我们将通过编写一个简单的P

重复采样魔法:用更多样本击败单次尝试的最强模型

这篇文章探讨了通过增加生成样本的数量来扩展大型语言模型(LLMs)在推理任务中的表现。 研究发现,重复采样可以显著提高模型的覆盖率,特别是在具有自动验证工具的任务中。研究还发现,覆盖率与样本数量之间的关系可以用指数幂律建模,揭示了推理时间的扩展规律。尽管多数投票和奖励模型在样本数量增加时趋于饱和,但在没有自动验证工具的任务中,识别正确样本仍然是一个重要的研究方向。 总体而言,重复采样提供了一种

图形API学习工程(0):工程目的环境配置

工程目的 我想要不借助引擎,而直接使用底层图形API(如DirectX和OpenGL等)来生成图像。 我认为这将有利于图形学算法与渲染框架相关的学习,因为: 游戏引擎往往对渲染进行了豪华的封装,而不利于看到图形学算法本质。UE4虽然开放了源代码,但是想要完全掌握渲染方面的代码也需要较高成本。 另外,我想对不止一个主流API进行封装,而是多个图形API进行封装,包括: OpenGLD3D1

07_TensorFlow2图像编解码大揭秘:让图片说‘变’就‘变’,魔法还是科技?

1. 图像的编码和解码 在实际应用中,图像数据源格式多种多样,如:png\jpg\bmp等,而神经网络训练模型所需的图像的数据格式为:图像字节数据或Base64编码数据等。基于此,将png\jpg\bmp等格式的图像转换为字节数据的过程称为图像编码,将字节数据的图像转换为png\jpg\bmp等格式图像的过程称为图像解码。 2. 图像编码 Tensorflow图像编码的过程如下图所示,分

公司数字化转型的目的是什么?

不同行业公司,其数字化转型的目的也不一样。下面我列举几个行业,给大家讲讲其数字化转型的真正目的。 制造数字化转型 制造业来说,数字化转型的本质是通过新一代信息技术与制造技术的融合,实现以数据为核心的资源要素变革、以网络化为牵引的生产方式重构、以扁平化为方向的企业形态转型、以平台赋能为导向的业务模式创新;构建全感知、全联接、全场景、全智能的数字工厂,优化产品的研发生产和营销流程,对传统管

读软件设计的要素02概念的目的

1. 要素 1.1. 概念的定义包括名称、目的、状态、操作和操作原则 1.2. 操作原则(operational principle) 1.2.1. 操作原则用于展示如何通过操作实现目的,这是理解概念的关键 1.2.2. 展示如何通过操作的组合实现概念的目的,包含一个或多个典型的使用场景 1.2.3. 操作原则并没有增加任何信息,因为你完全可以从操作规范中推理出任何使用场景 1

LeetCode题解:2341. 数组能形成多少数对,哈希表,详细注释

原题链接 LeetCode题解:2341. 数组能形成多少数对 解题思路: 遍历数组,并使用Map缓存数字出现的次数关系 如果出现偶数次,map.set(num, true)如果出现奇数次,map.set(num, false) 剩余数字的数量为nums.length - 2 * pairCount /*** @param {number[]} nums* @return {number[

【Jupyter】 Notebook 中的 IPython 魔法:12个必知实用技巧

Jupyter Notebook 作为一个强大的交互式计算环境,结合 IPython 的功能,为数据科学家和程序员提供了丰富的工具。本文将介绍12个在 Jupyter Notebook 中使用 IPython 的实用技巧 1. 清除输出:使用 clear_output() from IPython.display import clear_output# 执行一些操作print("This