【算法|贪心算法系列No.2】leetcode2208. 将数组和减半的最少操作次数

个人主页:兜里有颗棉花糖
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创
收录于专栏【手撕算法系列专栏】【LeetCode】
🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助
🍓希望我们一起努力、成长,共同进步
在这里插入图片描述

点击直接跳转到该题目

目录

  • 1️⃣题目描述
  • 2️⃣题目解析
  • 3️⃣解题代码

1️⃣题目描述

给你一个正整数数组 nums 。每一次操作中,你可以从 nums 中选择 任意 一个数并将它减小到 恰好 一半。(注意,在后续操作中你可以对减半过的数继续执行操作)

请你返回将 nums 数组和 至少 减少一半的 最少 操作数。

示例 1:

输入:nums = [5,19,8,1]
输出:3
解释:初始 nums 的和为 5 + 19 + 8 + 1 = 33 。
以下是将数组和减少至少一半的一种方法:
选择数字 19 并减小为 9.5 。
选择数字 9.5 并减小为 4.75 。
选择数字 8 并减小为 4 。
最终数组为 [5, 4.75, 4, 1] ,和为 5 + 4.75 + 4 + 1 = 14.75 。
nums 的和减小了 33 - 14.75 = 18.25 ,减小的部分超过了初始数组和的一半,18.25 >= 33/2 = 16.5 。
我们需要 3 个操作实现题目要求,所以返回 3 。
可以证明,无法通过少于 3 个操作使数组和减少至少一半。

示例 2:

输入:nums = [3,8,20]
输出:3
解释:初始 nums 的和为 3 + 8 + 20 = 31 。
以下是将数组和减少至少一半的一种方法:
选择数字 20 并减小为 10 。
选择数字 10 并减小为 5 。
选择数字 3 并减小为 1.5 。
最终数组为 [1.5, 8, 5] ,和为 1.5 + 8 + 5 = 14.5 。
nums 的和减小了 31 - 14.5 = 16.5 ,减小的部分超过了初始数组和的一半, 16.5 >= 31/2 = 15.5 。
我们需要 3 个操作实现题目要求,所以返回 3 。
可以证明,无法通过少于 3 个操作使数组和减少至少一半。

注意:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 107

2️⃣题目解析

本题不是很复杂,并没有很明显的使用贪心策略,只是简单的使用优先队列(堆)来动态地获取数组中的最大值并将其逐步减半,直到元素的和不超过原始数组元素和的一半

3️⃣解题代码

class Solution {
public:int halveArray(vector<int>& nums) {priority_queue<double> heap;double sum = 0.0;int count = 0;for(int x : nums){heap.push(x);sum += x;}sum /= 2;while(sum > 0){double tmp = heap.top() / 2.0;sum -= tmp;heap.pop();count++;heap.push(tmp);}return count;}
};

最后就通过啦:
在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/146602.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【办公自动化】在Excel中按条件筛选数据并存入新的表(文末送书)

&#x1f935;‍♂️ 个人主页&#xff1a;艾派森的个人主页 ✍&#x1f3fb;作者简介&#xff1a;Python学习者 &#x1f40b; 希望大家多多支持&#xff0c;我们一起进步&#xff01;&#x1f604; 如果文章对你有帮助的话&#xff0c; 欢迎评论 &#x1f4ac;点赞&#x1f4…

分享46个Python源代码总有一个是你想要的

分享46个Python源代码总有一个是你想要的 下载链接&#xff1a;https://pan.baidu.com/s/1oZPrXHwgzcvVpB36_dA72A?pwd8888 提取码&#xff1a;8888 chat-web项目的python后端 Django WEB商城网站项目 django-实时接口获取中国各个城市、省份、国家的新型冠状肺炎 NewsSp…

蓝桥杯每日一题2023.10.2

时间显示 - 蓝桥云课 (lanqiao.cn) 题目描述 题目分析 输入为毫秒&#xff0c;故我们可以先将毫秒转化为秒&#xff0c;由于只需要输出时分&#xff0c;我们只需要将天数去除即可&#xff0c;可以在这里多训练一次天数判断 #include<bits/stdc.h> using namespace std…

电子地图 | VINS-FUSION | 小觅相机D系列

目录 一、相关介绍 二、VINS-FUSION环境安装及使用 &#xff08;一&#xff09;Ubuntu18.04安装配置 1、Ubuntu下载安装 2、设置虚拟内存&#xff08;可选&#xff09; &#xff08;二&#xff09;VINS-FUSION环境配置 1、ros安装 2、ceres-solver安装 3、vins-fusion…

微服务moleculer03

1. Moleculer 目前支持SQLite&#xff0c;MySQL&#xff0c;MariaDB&#xff0c;PostgreSQL&#xff0c;MSSQL等数据库&#xff0c;这里以mysql为例 2. package.json 增加mysql依赖 "mysql2": "^2.3.3", "sequelize": "^6.21.3", &q…

docker基础命令

目录 一、安装docker 1、查看是否已安装docker 2、如果系统中已经存在旧的Docker 3、配置Docker的yum库 4、安装成功后&#xff0c;执行命令&#xff0c;配置Docker的yum源 5、安装Docker 6、启动和校验 7、配置镜像加速器&#xff0c;阿里云镜像加速为例 7.1、在首页的…

LabVIEW开发虚拟与现实融合的数字电子技术渐进式实验系统

LabVIEW开发虚拟与现实融合的数字电子技术渐进式实验系统 数字电子技术是所有电气专业的重要学科基础&#xff0c;具有很强的理论性和实践性。其实验是提高学生分析、设计和调试数字电路能力&#xff0c;培养学生解决实际问题的工程实践能力&#xff0c;激发学生创新意识&…

38 翻转二叉树

翻转二叉树 理解题意&#xff0c;翻转即每个结点的左右子树翻转/对调题解1 递归——自下而上题解2 迭代——自上而下 给你一棵二叉树的根节点 root &#xff0c;翻转这棵二叉树&#xff0c;并返回其根节点。 提示&#xff1a; 树中节点数目范围在 [0, 100] 内-100 < Node.…

开源博客项目Blog .NET Core源码学习(3:数据库操作方式)

开源博客项目Blog采用SqlSugar模块连接并操作数据库&#xff0c;本文学习并记录项目中使用SqlSugar的方式和方法。   首先&#xff0c;数据库连接信息放在了App.Hosting项目的appsettings.json中DbConfig节&#xff0c;支持在DbConfig节配置多个数据库连接信息&#xff0c;以…

探索腾讯企业邮箱替代方案:选择适合你的新邮件服务

腾讯企业邮箱作为一款广受欢迎的企业级电子邮件服务&#xff0c;已经在国内市场占据了相当大的份额。然而&#xff0c;随着全球市场竞争的加剧&#xff0c;腾讯企业邮箱也面临着海外市场的挑战。本文将探讨腾讯企业邮箱出海的劣势&#xff0c;并推荐一些替代品牌&#xff0c;以…

多线程 - 阻塞式队列

阻塞队列 阻塞队列,也是一个队列 ~~ 先进先出 实际上有一些特殊的队列,不一定非得遵守先进先出的 ~~ 优先级队列(PriorityQueue) 阻塞队列,也是特殊的队列,虽然也是先进先出的,但是带有特殊的功能: 阻塞 如果队列为空,执行出队列操作,就会阻塞.阻塞到另一个线程往队列里添加元…

软件测试之Python基础学习

目录 一、Python基础 Python简介、环境搭建及包管理 Python简介 环境搭建 包管理 Python基本语法 缩进(Python有非常严格的要求) 一行多条语句 断行 注释 变量 基本数据类型(6种) 1. 数字Number 2. 字符串String 3. 列表List 4. 元组Tuple 序列相关操作方法 …

gitlab配置webhook限制提交注释

一、打开gitlab相关配置项 vim /etc/gitlab/gitlab.rb gitlab_shell[custom_hooks_dir] "/etc/gitlab/custom_hooks" 二、创建相关文件夹 mkdir -p /etc/gitlab/custom_hooks mkdir -p /etc/gitlab/custom_hooks/post-receive.d mkdir -p /etc/gitlab/custom_h…

[Linux 基础] 一篇带你了解linux权限问题

文章目录 1、Linux下的两种用户2、文件类型和访问权限&#xff08;事物属性&#xff09;2.1 Linux下的文件类型2.2 基本权限2.3 文件权限值的表示方法&#xff08;1&#xff09;字符表示方法&#xff08;2&#xff09;8进制数值表示方法 2.4 文件访问权限的相关设置方法(1) chm…

《 新手》web前端(axios)后端(java-springboot)对接简解

文章目录 <font color red>1.何为前后端对接?2.对接中关于http的关键点2.1. 请求方法2.2. 请求参数设置简解&#xff1a; 3.对接中的跨域(CROS)问题**为什么后端处理跨域尽量在业务之前进行&#xff1f;**3.总结 1.何为前后端对接? “前后端对接” 是指前端和后端两个…

【VR】【unity】如何在VR中实现远程投屏功能?

【背景】 目前主流的VD应用,用于娱乐很棒,但是用于工作还是无法效率地操作键鼠。用虚拟键盘工作则显然是不现实的。为了让自己的头显能够起到小面积代替多显示屏的作用,自己动手开发投屏VR应用。 【思路】 先实现C#的投屏应用。研究如何将C#投屏应用用Unity 3D项目转写。…

【开发篇】十三、J2cache缓存框架

文章目录 1、介绍2、二级缓存下数据的读取与更新3、整合4、使用举例5、配置的相关说明6、小结 1、介绍 J2cache是一个缓存整合框架&#xff0c;可以提供缓存的整合方案&#xff0c;使各种缓存搭配使用&#xff0c;自身不提供缓存功能。 J2cache是一个两次缓存的框架 第一级缓存…

国庆中秋特辑(五)MySQL如何性能调优?下篇

目录 5.数据库维护6. 数据库调优工具7.数据库架构优化8.代码层面优化9. 硬件层面优化10. 数据库安全 MySQL 性能优化是一项关键的任务&#xff0c;可以提高数据库的运行速度和效率。以下是一些优化方法&#xff0c;包括具体代码和详细优化方案。 接下来详细介绍&#xff0c;共有…

第1篇 目标检测概述 —(3)YOLO系列算法

前言&#xff1a;Hello大家好&#xff0c;我是小哥谈。YOLO&#xff08;You Only Look Once&#xff09;系列算法是一种目标检测算法&#xff0c;主要用于实时物体检测。相较于传统的目标检测算法&#xff0c;YOLO具有更快的检测速度和更高的准确率。YOLO系列算法的核心思想是将…

企业怎样选择适合的服务器租用?

随着互联网技术的发展&#xff0c;如何选择企业需要的服务器租用来满足需求是很多企业目前在考虑的问题&#xff0c;今天就让小编来给大家讲一讲吧&#xff01; 确定好服务器的规模和用途。企业首先根据自身的业务情况选择服务器的数量和规模还有性能&#xff0c;小型企业可以…