Leetcode力扣秋招刷题路-2335
从0开始的秋招刷题路,记录下所刷每道题的题解,帮助自己回顾总结
2335. 装满杯子需要的最短总时长
现有一台饮水机,可以制备冷水、温水和热水。每秒钟,可以装满 2 杯 不同 类型的水或者 1 杯任意类型的水。
给你一个下标从 0 开始、长度为 3 的整数数组 amount ,其中 amount[0]、amount[1] 和 amount[2] 分别表示需要装满冷水、温水和热水的杯子数量。返回装满所有杯子所需的 最少 秒数。
示例 1:
输入:amount = [1,4,2]
输出:4
解释:下面给出一种方案:
第 1 秒:装满一杯冷水和一杯温水。
第 2 秒:装满一杯温水和一杯热水。
第 3 秒:装满一杯温水和一杯热水。
第 4 秒:装满一杯温水。
可以证明最少需要 4 秒才能装满所有杯子。
示例 2:
输入:amount = [5,4,4]
输出:7
解释:下面给出一种方案:
第 1 秒:装满一杯冷水和一杯热水。
第 2 秒:装满一杯冷水和一杯温水。
第 3 秒:装满一杯冷水和一杯温水。
第 4 秒:装满一杯温水和一杯热水。
第 5 秒:装满一杯冷水和一杯热水。
第 6 秒:装满一杯冷水和一杯温水。
第 7 秒:装满一杯热水。
示例 3:
输入:amount = [5,0,0]
输出:5
解释:每秒装满一杯冷水。
提示:
amount.length == 3
0 <= amount[i] <= 100
贪心:尽可能多的装两杯,总次数就是sum(a[i]) / 2 (上取整)
如果a[0], a[1], a[2]其中某一个数>=另外两个,那总次数就是a[i]_max,
法一: 数学问题
class Solution {
public:int fillCups(vector<int>& a) {sort(a.begin(), a.end());if (a[0] + a[1] <= a[2]) return a[2];return (a[0] + a[1] + a[2] + 1) / 2;}
};
优化
class Solution {
public:int fillCups(vector<int>& a) {return max({a[0], a[1], a[2], (a[0] + a[1] + a[2] + 1) / 2}); //注意这里要加 max( { } ) ;}
};
法二:堆 (本质和排序一样)
思路 :
把数组建成大根堆。
每一次都尽量装 2 杯不同的水 ( 每次都取出最大值t1和次大值t2 )
2.1 若!t1 直接break返回res (整个堆的元素都是 0 )
2.2 若t1 >= 1 && t2 >= 1,就装这两杯水 同时heap.insert(t1 - 1 and t2 - 1)
2.3 若t1 >= 1 && !t2 ,res += t1,然后break返回res
注意: 我们只关心剩余的杯数量,而不关心具体装的是什么水,所以只需要维护剩余杯数的具体数值即可,不需要知道其对应的水的属性
class Solution {
public:int fillCups(vector<int>& amount) {// greedy -> 每次都尽量装两杯满水int res = 0;priority_queue<int> heap; // 大根堆for (auto &x: amount)heap.push(x);while (heap.size()){int t1 = heap.top();heap.pop();int t2 = heap.top();heap.pop();if (!t1) break; // 当前队列最大值是 0 说明所有 amount 都装满了 if (t1 >= 1 && t2 >= 1){heap.push(t1 - 1);heap.push(t2 - 1);}else if (t1 >= 1 && !t2){res += t1;break;}res ++;}return res;}
};
相关文章:
Leetcode力扣秋招刷题路-2335
从0开始的秋招刷题路,记录下所刷每道题的题解,帮助自己回顾总结 2335. 装满杯子需要的最短总时长 现有一台饮水机,可以制备冷水、温水和热水。每秒钟,可以装满 2 杯 不同 类型的水或者 1 杯任意类型的水。 给你一个下标从 0 开…...
C语言深度解剖-关键字(6)
目录 1. 浮点型与零的比较: 1.1 推导: 1.2 实践: 总结: 理解强制类型转换: 指针与零比较 switch case 语句: 写在最后: 1. 浮点型与零的比较: 1.1 推导: 例&am…...
[多线程进阶]CAS与Synchronized基本原理
专栏简介: JavaEE从入门到进阶 题目来源: leetcode,牛客,剑指offer. 创作目标: 记录学习JavaEE学习历程 希望在提升自己的同时,帮助他人,,与大家一起共同进步,互相成长. 学历代表过去,能力代表现在,学习能力代表未来! 目录: 1.CAS 1.1 什么是CAS? 1.2 CAS伪代码 1.3 CAS …...
【Linux系统编程】02:文件操作
文件IO 系统调用(不带缓冲的IO操作)库函数(默认带用户缓冲的IO操作) 一、非缓冲IO 系统调用:即为不带缓冲的IO 1.打开文件open 2.读取文件read NAMEread - read from a file descriptorSYNOPSIS#include <unist…...
华为OD机试 - 去除多余空格(Python)| 真题+思路+代码
去除多余空格 题目 去除文本多余空格,但不去除配对单引号之间的多余空格。给出关键词的起始和结束下标,去除多余空格后刷新关键词的起始和结束下标。 条件约束: 不考虑关键词起始和结束位置为空格的场景;单词的的开始和结束下标保证涵盖一个完整的单词,即一个坐标对开…...
百趣代谢组学分享,补充α-酮酸的低蛋白饮食对肾脏具有保护作用
文章标题:Reno-Protective Effect of Low Protein Diet Supplemented With α-Ketoacid Through Gut Microbiota and Fecal Metabolism in 5/6 Nephrectomized Mice 发表期刊:Frontiers in Nutrition 影响因子:6.59 作者单位:…...
json对象和formData相互转换
前言 大家都知道,前端在和后台进行交互联调时,肯定避免不了要传递参数,一般情况下,params 在 get 请求中使用,而 post 请求下,我们有两种常见的传参方式: JSON 对象格式和 formData 格式&#x…...
【c++面试问答】常量指针和指针常量的区别
问题 常量指针和指针常量有什么区别? const的优点 在C中,关键字const用来只读一个变量或对象,它有以下几个优点: 便于类型检查,如函数的函数 func(const int a) 中a的值不允许变,这样便于保护实参。功能…...
Ubuntu18下编译android的ffmpeg经验
虽然按照网上的一些资料(如:最简单的基于FFmpeg的移动端例子:Android HelloWorld_雷霄骅的博客-CSDN博客_android ffmpeg 例子,,编译FFmpeg4.1.3并移植到Android app中使用(最详细的FFmpeg-Android编译教程…...
Spring Security in Action 第十三章 实现OAuth2的认证端
本专栏将从基础开始,循序渐进,以实战为线索,逐步深入SpringSecurity相关知识相关知识,打造完整的SpringSecurity学习步骤,提升工程化编码能力和思维能力,写出高质量代码。希望大家都能够从中有所收获&#…...
本文章提供中国国界、国界十段线原始数据以及加载方法
本文章提供中国国界九段线原始数据和加载方法 1、中国国界 完整数据 包括十段线 中国国界线(完整版 包括十段线) 2、原始数据 中国国界十段线topojson格式数据.rar 中国国界线topjson数据 中国国界十段线svg格式数据.rar 中国国界线svg数据 中国国界十段线shp格式数据…...
一文带你搞懂,Python语言运算符
Python语言支持很多种运算符,我们先用一个表格为大家列出这些运算符,然后选择一些马上就会用到的运算符为大家进行讲解。 说明:上面这个表格实际上是按照运算符的优先级从上到下列出了各种运算符。所谓优先级就是在一个运算的表达式中&#x…...
JAVA集合专题4 —— Map
目录Map接口实现类的特点Map接口的常见方法Map六大遍历方式Map练习1code编程练习2code编程练习3思路codeMap接口实现类的特点 Map与Collection并列存在,是Map集合体系的顶级接口Map的有些子实现存储数据是有序的(LinkedHashMap),有些子实现存储数据是无…...
二叉树进阶--二叉搜索树
目录 1.二叉搜索树 1.1 二叉搜索树概念 1.2 二叉搜索树操作 1.3 二叉搜索树的实现 1.4 二叉搜索树的应用 1.5 二叉搜索树的性能分析 2.二叉树进阶经典题: 1.二叉搜索树 1.1 二叉搜索树概念 二叉搜索树又称二叉排序树,它或者是一棵空树,…...
牛客网Python篇数据分析习题(三)
1.现有一个Nowcoder.csv文件,它记录了牛客网的部分用户数据,包含如下字段(字段与字段之间以逗号间隔): Nowcoder_ID:用户ID Level:等级 Achievement_value:成就值 Num_of_exercise&a…...
Java开发常见关键词集绵
一、关键词1: (1)RPC:远程过程调用(Remote Procedure Call)的缩写形式。远程调用的时候让人们觉得是本地调用。 (2)HTTP:超文本传输协议(Hyper Text Transfer…...
解决idea出现的java.lang.OutOfMemoryError: Java heap space的问题
文章目录1. 复现问题2. 分析问题3. 解决问题4. 补充解决java.lang.OutOfMemoryError: PermGen space问题1. 复现问题 今天使用idea开发时,突然报出如下错误: Exception in thread "main" java.lang.OutOfMemoryError: Java heap spaceat org.…...
为什么子进程要继承处理器亲缘性?
请先考虑一个典型的程序为什么需要启动一个子进程。(当然资源管理器不算一个典型的程序) 这是因为手头的任务被分解为子任务,无论出于何种原因,这些子任务都被放入子流程中。例如,在实现多次遍历型编译器/链接器时,其中每次遍历都…...
【算法】高精度
作者:指针不指南吗 专栏:算法篇 🐾不能只会思路,必须落实到代码上🐾 文章目录前言一、高精度加法二、高精度减法三、高精度乘法四、高精度除法前言 高精度即很大很大的数,超过了 long long 的范围&…...
计算机网络-基本概念
目录 计算机网络-基本概念 互联网 Java的跨平台原理 编辑 C\C的跨平台原理 解释性语言的跨平台原理(python,js等) 客户端 vs 服务器 什么是协议? 网络互连模型 请求过程 计算机之间的通信基础 计算机之间的连接方式-网线直连(需要用交叉线,而…...
你评论,我赠书~【哈士奇赠书 - 13期】-〖Python程序设计-编程基础、Web开发及数据分析〗参与评论,即可有机获得
大家好,我是 哈士奇 ,一位工作了十年的"技术混子", 致力于为开发者赋能的UP主, 目前正在运营着 TFS_CLUB社区。 💬 人生格言:优于别人,并不高贵,真正的高贵应该是优于过去的自己。💬 ὎…...
【设计模式】我终于读懂了代理模式。。。
👦代理模式的基本介绍 1)代理模式:为一个对象提供一个替身,以控制对这个对象的访问。即通过代理对象访问目标对象,这样做的好处是:可以在目标对象实现的基础上,增强额外的功能操作,即扩展目标对象的功能。 2)被代理的对象可以是远程对象、创建…...
每天10个前端小知识 【Day 2】
👩 个人主页:不爱吃糖的程序媛 🙋♂️ 作者简介:前端领域新星创作者、CSDN内容合伙人,专注于前端各领域技术,成长的路上共同学习共同进步,一起加油呀! ✨系列专栏:前端…...
帮助中心在线制作工具推荐这4款,很不错哟!
根据用户咨询问题是否解决的情景,分为三个部分,首先帮助中心恰好有用户需要咨询的问题,用户可以通过点击相关问题即可解决自己的问题,其次,用户第一眼没有在帮助中心解决问题,有个搜索框,用户的…...
rabbitMQ相关文章汇总
RabbitMQ五种工作模式: https://blog.csdn.net/weixin_41882200/article/details/117128590?ops_request_misc%257B%2522request%255Fid%2522%253A%2522167625223516800182771874%2522%252C%2522scm%2522%253A%252220140713.130102334…%2522%257D&request_id1…...
【C++】异常
🌈欢迎来到C专栏~~异常 (꒪ꇴ꒪(꒪ꇴ꒪ )🐣,我是Scort目前状态:大三非科班啃C中🌍博客主页:张小姐的猫~江湖背景快上车🚘,握好方向盘跟我有一起打天下嘞!送给自己的一句鸡汤…...
@Validated注解不生效问题汇总
Validated注解不生效问题汇总 文章目录Validated注解不生效问题汇总背景:一:可能原因原因1:原因2:原因3:原因4:二:补充全局异常对validation的处理背景: 项目框架应用的是validatio…...
华科万维C++章节练习2_4
题目:编写程序,从键盘输入一个字符,然后在屏幕上输出该字符开头的连续3个字符以及对应ASCII码。 输出格式请参看: 请输入一个字符>>A 字符 ASCII码 A 65 B 66 C 67 请按任意键继续. . . 请直接…...
17万字数字化医院信息化建设大数据平台建设方案WORD
【版权声明】本资料来源网络,知识分享,仅供个人学习,请勿商用。【侵删致歉】如有侵权请联系小编,将在收到信息后第一时间删除!完整资料领取见文末,部分资料内容: 目录 第1章 医院信息化概述 1.…...
Android 11系统签名修改
Android OS 映像在两个地方使用加密签名:映像中的所有 .apk 文件都必须经过签名。Android 软件包管理器通过下列两种方式使用 .apk 签名:更换应用时,必须使用与旧应用相同的密钥对其签名,才能存取旧应用的数据。无论是通过覆盖 .a…...
中国建设银行邀约提额网站/扬州百度推广公司
1、查找某条数据的创建时间同个月内的所有数据 SELECT * FROM 表名 WHERE DATE_FORMAT( create_time, %Y%m ) DATE_FORMAT( 2021-01-01 , %Y%m ) create_time:表里表示创建时间的字段名 2021-01-01 :选择的某条数据创建时间的年月日 2、使用select…...
地坪漆东莞网站建设技术支持/辽宁网站建设
我们在有些开发时候可能会用到些头条的文章,,添加过程如下所示: 我们在前台遍历数据的时候可以这样, 然后在后台更新首页模版后在去看下首页,效果如下所示: 转载于:https://www.cnblogs.com/leigood/p/5301…...
做网站运营好还是SEO好/网站登录入口
怎么设置legacy启动?现在新型电脑都是采用uefi gpt启动模式,以适应win8、win10这些新型操作系统,不过win7之前的系统大多不支持uefi,而是采用legacy启动模式,硬盘分区表是MBR,而不是GPT,如果要在…...
网站无域名注册人id/加盟培训机构
1、次数分配数列是()。(2 分) A.按数量标志分组形成的数列 B.按品质标志分组形成的数列 C.按统计指标分组所形成的数列 D.按数量标志和品质标志分组所形成的数列 2、下列指标中属于时…...
福州网站建设/emlog友情链接代码
数据结构C语言版清华大学严蔚敏(学习笔记总结1,代码在下面)——顺序表、链表、循环链表、双向链表、结点的插入删除(前面是笔记方便理解,最下面有详细代码)_玛卡巴卡的博客-CSDN博客 串(即字符…...
手机网站app制作/天津百度推广电话号码
修复此问题 禁用内核调试,在 Visual Studio 中调试。- 或 -使用内核调试器而不是 Visual Studio 进行调试。- 或 -在内核调试器中禁用用户模式异常。在当前会话中禁用内核调试 在命令提示处,键入: 复制代码 Kdbgctrl.exe -d对所有会话禁用内核…...