当前位置: 首页 > news >正文

Leetcode.2171 拿出最少数目的魔法豆

题目链接

Leetcode.2171 拿出最少数目的魔法豆 Rating : 1748

题目描述

给你一个 整数数组 beans,其中每个整数表示一个袋子里装的魔法豆的数目。

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

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

示例 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<=1051 <= beans.length <= 10^51<=beans.length<=105
  • 1<=beans[i]<=1051 <= beans[i] <= 10^51<=beans[i]<=105

解法:排序

我们先将豆子 beans按从小到大的顺序排序。

在这里插入图片描述

蓝色的就是要剩下来的豆子,白色的就是要拿走的豆子。

我们用 sum记录所有的豆子。

蓝色部分的豆子:beans[i]∗(n−i)beans[i] * (n - i)beans[i](ni)

白色部分的豆子(要拿走的豆子): sum−beans[i]∗(n−i)sum - beans[i] * (n - i)sumbeans[i](ni)

所以我们只需要从 i=0i = 0i=0遍历到 i=n−1i = n - 1i=n1,遍历一遍,用一个 ans记录最小值即可。

时间复杂度:O(n∗logn)O(n * logn)O(nlogn)

C++代码:

using LL = long long;class Solution {
public:long long minimumRemoval(vector<int>& beans) {LL sum = accumulate(beans.begin(),beans.end(),0LL);sort(beans.begin(),beans.end());int n = beans.size();LL ans = 1e10;for(int i = 0;i < n;i++){ans = min(ans , sum - (n - i) * 1LL * beans[i]);}return ans;}
};

相关文章:

Leetcode.2171 拿出最少数目的魔法豆

题目链接 Leetcode.2171 拿出最少数目的魔法豆 Rating &#xff1a; 1748 题目描述 给你一个 正 整数数组 beans&#xff0c;其中每个整数表示一个袋子里装的魔法豆的数目。 请你从每个袋子中 拿出 一些豆子&#xff08;也可以 不拿出&#xff09;&#xff0c;使得剩下的 非空…...

day1 计算机组成与结构考点汇总

一、重点知识点 计算机硬件组成、运算器、控制器奇偶校验码、循环冗余校验码、海明码指令系统&#xff1a;指令操作数寻址方式、CISC和RISC、指令流水线的计算存储系统&#xff1a;分级存储、局部性原理、cache、主存编址计算、磁盘输入输出技术&#xff1a;程序查询方式、中断…...

Java虚拟机的类加载机制

Java虚拟机的类加载机制综述类的生命周期类加载器双亲委派模型---综述 我们编写的Java代码如何能在一个操作系统上运行呢&#xff1f;一般来说&#xff0c;我们使用javac命令将.java文件编译成.class文件&#xff0c;也就是Java字节码文件&#xff0c;然后由JVM将字节码文件加…...

分治法实现合并排序(归并排序),理解分治算法思想,实现分治算法的完美例子合并排序(含码源与解析)

&#x1f38a;【数据结构与算法】专题正在持续更新中&#xff0c;各种数据结构的创建原理与运用✨&#xff0c;经典算法的解析✨都在这儿&#xff0c;欢迎大家前往订阅本专题&#xff0c;获取更多详细信息哦&#x1f38f;&#x1f38f;&#x1f38f; &#x1fa94;本系列专栏 -…...

Typescript 类 (class)

基本用法 (通过关键字 class) // 基本用法 class VueService {constructor() {} // 构造器 } 类的约束&#xff08;通过关键字 implements&#xff09; // 接口定义属性类型 interface VueProps {name: stringinit: () > void }// 约束类 class VueService implements Vue…...

KDZD程控超低频高压发生器

一、产品概述 本产品接合了现代数字变频技术&#xff0c;采用微机控制&#xff0c;升压、降压、测量、保护自动化。由于电子化&#xff0c;所以体积小重量轻、大屏幕液晶显示&#xff0c;清晰直观、且能显示输出波形、打印试验报告。 设计指标符合《电力设备专用测试仪器通用…...

【华为OD机试 2023最新 】 过滤组合字符串(C++)

文章目录 题目描述输入描述输出描述用例题目解析C++题目描述 数字0、1、2、3、4、5、6、7、8、9分别关联 a~z 26个英文字母。 0 关联 “a”,”b”,”c”1 关联 “d”,”e”,”f”2 关联 “g”,”h”,”i”3 关联 “j”,”k”,”l”4 关联 “m”,”n”,”o”5 关联 “p”,”q”…...

Java笔记034-坦克大战【2】

目录 坦克大战【2】 线程-应用到坦克大战 坦克大战0.3 思路分析&#xff1a; 代码实现&#xff1a; 坦克大战0.4 增加功能 特别说明 思路分析&#xff1a; 代码实现&#xff1a; 坦克大战0.5 增加功能 思路分析&#xff1a; 代码实现&#xff1a; 坦克大战【2】 …...

【算法】【数组与矩阵模块】桶排序思想解决无序数组排序后相邻数间的最大差值

目录前言问题介绍解决方案代码编写java语言版本c语言版本c语言版本思考感悟写在最后前言 当前所有算法都使用测试用例运行过&#xff0c;但是不保证100%的测试用例&#xff0c;如果存在问题务必联系批评指正~ 在此感谢左大神让我对算法有了新的感悟认识&#xff01; 问题介绍 …...

C语言—函数

函数库函数自定义函数函数的参数函数的调用函数的嵌套调用和链式访问函数的声明和定义函数递归递归与迭代函数递归的经典题目维基百科&#xff08;台湾方面维护的&#xff0c;翻译形式跟大陆有所差异&#xff09;中对函数的定义&#xff1a;子程序在计算机科学中&#xff0c;子…...

Autosar模式管理实战系列03-基于Davinci工具的WDGM配置

本文框架 前言1.WdgMConfigSet 配置2. 新建监控实体(SE)2.1 新建检测点(Checkpoint)2.2 设置 WdgMInternalTransitions3. WdgMLocalStatusParams配置4. WdgMAliveSupervision配置5. 代码插入指导前言 前面我们介绍了WdgM(看门狗管理)是一个 AutoSAR 的基础模块,负责管理看门…...

AutoML-sklearn and torch

一、auto-sklearn 1.1 环境依赖 额外安装swig 第三方库 linux 支持, mac&#xff0c;windows不支持 1.2 示例代码 time_left_for_this_task 设定任务最大时间 per_run_time_limit 每个子任务最大训练时间 include 可以限制任务训练的模型 import autosklearn.classific…...

《扬帆优配》算力概念股大爆发,主力资金大扫货

3月22日&#xff0c;9股封单金额超亿元&#xff0c;工业富联、鸿博股份、鹏鼎控股分别为3.01亿元、2.78亿元、2.37亿元。 今日三大指数团体收涨&#xff0c;收盘共34股涨停&#xff0c;首要集中于数字经济方向&#xff0c;其间云核算、CPO大迸发。除去5只ST股&#xff0c;算计2…...

机械臂+底盘三维模型从solidworks到moveit配置功能包

文章目录 导出底盘STEP加载机械臂模型组合机械臂和底盘三维模型导出URDF在moveit中进行配置新建工作目录设置ROS工作空间的环境变量进入moveit setup加载URDF文件self-CollisionsPlanning groupsRobot posesControllersSimulationAuthor information生成配置包在rviz中进行可视…...

高并发系统设计:缓存、降级、限流、(熔断)

高并发系统设计&#xff1a;缓存、降级、限流、(熔断) 在开发高并发系统时有三把利器用来保护系统&#xff1a;缓存、降级和限流。 非核心服务可以采用降级、熔断&#xff0c;核心服务采用缓存和限流&#xff08;隔离流量可以最大限度的保障业务无损&#xff09;。 缓存 缓…...

《辉煌优配》放量大涨,A股成交额重回万亿!PCB板块继续领跑

多只绩优PCB概念股超跌。 今日A股放量反弹&#xff0c;成交额从头站上万亿关口。芯片板块掀涨停潮&#xff0c;景嘉微、芯原股份20cm涨停&#xff0c;紫光国微、兆易创新、跃岭股份等封板&#xff1b;AI算力、存储器、光模块、云核算等板块全线拉升&#xff0c;板块内个股再度批…...

Vue封装的过度与动画

动画效果 先把样式封装好&#xff0c;然后设置一个动画 不需要vue也能实现的动画的效果&#xff0c;我们只需要判断一下&#xff0c;然后动态的添加和删除类名即可 那能不能不自己写动态&#xff0c;就靠vue 首先我们要靠<transition>标签把需要动画的包裹起来 vue中…...

流量监控-ntopng

目录介绍安装使用介绍 ntopng是原始ntop的下一代版本&#xff0c;ntop是监视网络使用情况的网络流量探测器。ntopng基于libpcap&#xff0c;并且以可移植的方式编写&#xff0c;以便实际上可以在每个Unix平台&#xff0c;MacOSX和Windows上运行。 ntopng&#xff08;是的&…...

C++ 21 set容器

目录 一、set容器 1.1 简介 1.2 构造和赋值 1.3 大小和交换 1.4 插入和删除 1.5 查找和统计 1.6 set和multiset区别 1.7 内置类型指定排序规则 1.8 自定义数据类型指定排序规则 一、set容器 1.1 简介 ① set容器中所有元素在插入时自动被排序。 ② set容器和multise…...

什么是JWT

JSON Web Token&#xff08;缩写 JWT&#xff09;是目前最流行的跨域认证解决方案。 传统的session认证 http协议本身是一种无状态的协议&#xff0c;而这就意味着如果用户向我们的应用提供了用户名和密码来进行用户认证&#xff0c;那么下一次请求时&#xff0c;用户还要再一…...

地震勘探——干扰波识别、井中地震时距曲线特点

目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波&#xff1a;可以用来解决所提出的地质任务的波&#xff1b;干扰波&#xff1a;所有妨碍辨认、追踪有效波的其他波。 地震勘探中&#xff0c;有效波和干扰波是相对的。例如&#xff0c;在反射波…...

Leetcode 3577. Count the Number of Computer Unlocking Permutations

Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接&#xff1a;3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯&#xff0c;要想要能够将所有的电脑解锁&#x…...

相机从app启动流程

一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...

DBAPI如何优雅的获取单条数据

API如何优雅的获取单条数据 案例一 对于查询类API&#xff0c;查询的是单条数据&#xff0c;比如根据主键ID查询用户信息&#xff0c;sql如下&#xff1a; select id, name, age from user where id #{id}API默认返回的数据格式是多条的&#xff0c;如下&#xff1a; {&qu…...

dify打造数据可视化图表

一、概述 在日常工作和学习中&#xff0c;我们经常需要和数据打交道。无论是分析报告、项目展示&#xff0c;还是简单的数据洞察&#xff0c;一个清晰直观的图表&#xff0c;往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server&#xff0c;由蚂蚁集团 AntV 团队…...

【Redis】笔记|第8节|大厂高并发缓存架构实战与优化

缓存架构 代码结构 代码详情 功能点&#xff1a; 多级缓存&#xff0c;先查本地缓存&#xff0c;再查Redis&#xff0c;最后才查数据库热点数据重建逻辑使用分布式锁&#xff0c;二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...

4. TypeScript 类型推断与类型组合

一、类型推断 (一) 什么是类型推断 TypeScript 的类型推断会根据变量、函数返回值、对象和数组的赋值和使用方式&#xff0c;自动确定它们的类型。 这一特性减少了显式类型注解的需要&#xff0c;在保持类型安全的同时简化了代码。通过分析上下文和初始值&#xff0c;TypeSc…...

给网站添加live2d看板娘

给网站添加live2d看板娘 参考文献&#xff1a; stevenjoezhang/live2d-widget: 把萌萌哒的看板娘抱回家 (ノ≧∇≦)ノ | Live2D widget for web platformEikanya/Live2d-model: Live2d model collectionzenghongtu/live2d-model-assets 前言 网站环境如下&#xff0c;文章也主…...

Modbus RTU与Modbus TCP详解指南

目录 1. Modbus协议基础 1.1 什么是Modbus? 1.2 Modbus协议历史 1.3 Modbus协议族 1.4 Modbus通信模型 🎭 主从架构 🔄 请求响应模式 2. Modbus RTU详解 2.1 RTU是什么? 2.2 RTU物理层 🔌 连接方式 ⚡ 通信参数 2.3 RTU数据帧格式 📦 帧结构详解 🔍…...

yaml读取写入常见错误 (‘cannot represent an object‘, 117)

错误一&#xff1a;yaml.representer.RepresenterError: (‘cannot represent an object’, 117) 出现这个问题一直没找到原因&#xff0c;后面把yaml.safe_dump直接替换成yaml.dump&#xff0c;确实能保存&#xff0c;但出现乱码&#xff1a; 放弃yaml.dump&#xff0c;又切…...