LeetCode-2335. 装满杯子需要的最短总时长【贪心,数学】
LeetCode-2335. 装满杯子需要的最短总时长【贪心,数学】
- 题目描述:
- 解题思路一:其实像一道数学题目。假设三个杯子x<=y<=z先分两种情况。第一种:x+y<=z,答案直接是最大的z。第二种:x+y>z。先将x与y互相匹配t次直到x+y<=z。那么t=(x+y-z)/2向上取整,即t>=1。取消向上取整则t=(x+y-z+1)/2,然后变回第一种情况,总的时长为t+z=(x+y+z+1)/2。
- 解题思路二:优化,一行代码!
- 解题思路三:比较费时但好理解的,排序然后大的两个数减1,记次数。
题目描述:
现有一台饮水机,可以制备冷水、温水和热水。每秒钟,可以装满 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
解题思路一:其实像一道数学题目。假设三个杯子x<=y<=z先分两种情况。第一种:x+y<=z,答案直接是最大的z。第二种:x+y>z。先将x与y互相匹配t次直到x+y<=z。那么t=(x+y-z)/2向上取整,即t>=1。取消向上取整则t=(x+y-z+1)/2,然后变回第一种情况,总的时长为t+z=(x+y+z+1)/2。
class Solution {
public:int fillCups(vector<int>& amount) {sort(amount.begin(),amount.end());if(amount[2]>=amount[0]+amount[1]) return amount[2];return (amount[0]+amount[1]+amount[2]+1)/2; }
};
时间复杂度:O(1)
空间复杂度:O(1)
解题思路二:优化,一行代码!
直接返回四个数中最大的那一个即可。
class Solution {
public:int fillCups(vector<int>& a) {return max({a[0], a[1], a[2], (a[0] + a[1] + a[2]+1)/2});}
};
时间复杂度:O(1)
空间复杂度:O(1)
解题思路三:比较费时但好理解的,排序然后大的两个数减1,记次数。
class Solution {
public:int fillCups(vector<int>& a) {int s=0;while(a[0]||a[1]||a[2]){sort(a.begin(),a.end());s++;if(a[1]) a[1]--;if(a[2]) a[2]--;}return s;}
};
相关文章:
LeetCode-2335. 装满杯子需要的最短总时长【贪心,数学】
LeetCode-2335. 装满杯子需要的最短总时长【贪心,数学】题目描述:解题思路一:其实像一道数学题目。假设三个杯子x<y<z先分两种情况。第一种:xy<z,答案直接是最大的z。第二种:xy>z。先将x与y互相…...
基于 oss 框架的音频驱动
基于 oss 框架完成系统平台音频驱动的适配。 oss 框架可被多个平台应用,因此 oss 提供 OS 目录来存放平台文件(比如:linux.c),该文件主要提供平台对 oss 框架封装后的相关接口。 以 Linux 为例,入口接口为…...
【golang】如何定制化zap日志库以及如何使用
Zap 日志 前言 本文主要介绍Go语言日志库如何简易定制化,以及如何在开发中使用。 为什么需要日志? 一个产品的诞生一定是因为有需求!新技术大部分都是为了更加便利和实用而诞生的,日志也不例外。日志顾名思义就是对整个项目的事件进行记…...
如何将 Ubuntu 升级到 22.04 LTS Jammy Jellyfish
在本教程中,我们将详细介绍如何将你的 Ubuntu 系统升级到版本 22.04 Jammy Jellyfish,这是最新的长期支持版本。 Ubuntu 22.04 LTS Jammy Jellyfish 将于 2022 年 4 月 21 日发布。它是下个两年一次的长期支持(LTS)版本,因此值得注意,而且现在 Ubuntu 21.10 的用户可以升…...
ubuntu20.04安装docker与docker-compose
安装docker 查看系统发行版本 cat /proc/version1、更新apt包 sudo apt-get update2、安装必备的软件包以允许apt通过 HTTPS 使用存储库(repository): sudo apt-get install ca-certificates curl gnupg lsb-release3、添加Docker官方版本…...
笔试题-2023-加特兰-数字IC设计【纯净题目版】
回到首页:2023 数字IC设计秋招复盘——数十家公司笔试题、面试实录 推荐内容:数字IC设计学习比较实用的资料推荐 题目背景 笔试时间:2022.07.27应聘岗位:数字电路设计工程师(SoC) - 2023届笔试时长:90min笔试平台:nowcoder牛客网题目类型:问答题(11道)主观评价 难易…...
动态内存管理
目录1.为什么要动态内存分配2.动态内存函数malloc](https://cplusplus.com/reference/cstdlib/malloc/?kwmalloc)和[freecallocrealloc3.使用动态内存要注意的几点对NULL的解引用对同一块动态内存多次释放free非动态开辟的内存使用free释放一块动态开辟内存的一部分一个函数中…...
Unsupervised Question Answering 简单综述
Unsupervised Question Answering by Cloze Translation, ACL 2019 随机从文本中抽取noun phrases或者named entity作为答案将答案部分mask掉,生成cloze question利用无监督翻译,将cloze question转化为natural question 缺点: 直接利用原句…...
智慧物流管理系统
智慧物流运用物联网、大数据、云计算、人工智能等技术优化物流决策过程。智慧物流获取、分析物流信息并做出决策,从商品源开始实时跟踪与管理,保证信息流快于商品流,实现信息与物质快速、高效、流畅地运转,集自动化、数字化、网络…...
单表查询--实例
#素材: 表名:worker-- 表中字段均为中文,比如 部门号 工资 职工号 参加工作 等 >CREATE TABLE worker ( >部门号 int(11) NOT NULL, >职工号 int(11) NOT NULL, >工作时间 date NOT NULL, >工资 float(8,2) NOT NULL, >政治…...
c语言递归 累和 ,累乘积,斐波那契数列,字符串长度
目录 递归使用场景 1:使用递归的方式计算 Sn123..100 2:计算 n!n*(n-1)*(n-2)*......*1; 3:计算输出斐波那契数列前20项,并按每行4个数的格式输出(2019年) 4: 用递归和非递归两种方式编写函数strlength()。该函数…...
数据与C(ASCII码,char)
目录 一.ASCII码讲解 二.非打印字符(转义字符) 三.扩展小知识 一.ASCII码讲解 char类型用于存储字符,从技术层面看,char时整数类型,因为char类型实际上存储的是整数而不是字符。计算机使用数字编码来处理字符&…...
第一个C语言代码(visual studin创建调试以及项目文件功能讲解)
这里我主要使用visual Studio进行编程 目录 一.创建项目 二.编写代码 1.代码编写 2.代码分析 3.main() 4.注释符 5.{} 花括号 6.声明 7.赋值 8.printf()函数 9.return 0; 一.创建项目 这里大家可能会比较疑惑,为啥都是C,没看见C的项目&…...
VIF原理
文章目录一、VIF公式和原理对于R方一般回归模型皮尔逊相关系数中的方差VIF原理:一、VIF公式和原理 所谓VIF方法,计算难度并不高。在线性回归方法里,应用最广泛的就是最小二乘法(OLS),只不过我们对每个因子…...
nginx相关反爬策略总结笔记
引言 互联网站点的流量一部分由人类正常访问行为产生,而高达30%-60%的流量则是由网络爬虫产生的,其中一部分包含友好网络爬虫,如搜索引擎的爬虫、广告程序、第三方合作伙伴程序、Robots协议友好程序等;而并非所有的网络爬虫都是友好的&#x…...
【Vue3】电商网站吸顶功能
头部分类导航-吸顶功能 电商网站的首页内容会比较多,页面比较长,为了能让用户在滚动浏览内容的过程中都能够快速的切换到其它分类。需要分类导航一直可见,所以需要一个吸顶导航的效果。 目标:完成头部组件吸顶效果的实现 交互要求 滚动距离大…...
HOMER docker版本安装详细流程
概述 HOMER是一款100%开源的针对SIP/VOIP/RTC的抓包工具和监控工具。 HOMER是一款强大的、运营商级、可扩展的数据包和事件捕获系统,是基于HEP/EEP协议的VoIP/RTC监控应用程序,并可以使用即时搜索、处理和存储大量的信令、RTC事件、日志和统计信息。 …...
【数据结构】单向链表的练习题
目录 前言 1、删除链表中等于给定值val的所有节点。 【题目描述】 【代码示例】 【 画图理解】 2、反转一个点链表 【题目描述】 【 代码思路】 【代码示例】 【画图理解】 3、给定一个带有头节点head的非空单链表,返回链表的中间节点,如果有两个…...
我的企业需要一个网站吗?答案是肯定的 10 个理由
如果您的企业在没有网站的情况下走到了这一步,您可能会想:我的企业需要一个网站吗?如果我的企业没有一个就已经成功了,那又有什么意义呢?简短的回答是,现在是为您的企业投资网站的最佳或更重要的时机。网站…...
CHI协议定义的NOC组件
请求结点RN 可以向NOC发送读/写等请求事务,有以下几种类型的RN: RN-F 一般是处理器核或者核簇结点,包含了局部cache和一致性部件snoopee。与NOC上的一致性部件一起,维护“可缓存”数据的一致性(这种可缓存数据…...
Vim 调用外部命令学习笔记
Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...
React 第五十五节 Router 中 useAsyncError的使用详解
前言 useAsyncError 是 React Router v6.4 引入的一个钩子,用于处理异步操作(如数据加载)中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误:捕获在 loader 或 action 中发生的异步错误替…...
OpenLayers 可视化之热力图
注:当前使用的是 ol 5.3.0 版本,天地图使用的key请到天地图官网申请,并替换为自己的key 热力图(Heatmap)又叫热点图,是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...
PHP和Node.js哪个更爽?
先说结论,rust完胜。 php:laravel,swoole,webman,最开始在苏宁的时候写了几年php,当时觉得php真的是世界上最好的语言,因为当初活在舒适圈里,不愿意跳出来,就好比当初活在…...
渲染学进阶内容——模型
最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...
智能仓储的未来:自动化、AI与数据分析如何重塑物流中心
当仓库学会“思考”,物流的终极形态正在诞生 想象这样的场景: 凌晨3点,某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径;AI视觉系统在0.1秒内扫描包裹信息;数字孪生平台正模拟次日峰值流量压力…...
【C++进阶篇】智能指针
C内存管理终极指南:智能指针从入门到源码剖析 一. 智能指针1.1 auto_ptr1.2 unique_ptr1.3 shared_ptr1.4 make_shared 二. 原理三. shared_ptr循环引用问题三. 线程安全问题四. 内存泄漏4.1 什么是内存泄漏4.2 危害4.3 避免内存泄漏 五. 最后 一. 智能指针 智能指…...
【从零开始学习JVM | 第四篇】类加载器和双亲委派机制(高频面试题)
前言: 双亲委派机制对于面试这块来说非常重要,在实际开发中也是经常遇见需要打破双亲委派的需求,今天我们一起来探索一下什么是双亲委派机制,在此之前我们先介绍一下类的加载器。 目录 编辑 前言: 类加载器 1. …...
MySQL:分区的基本使用
目录 一、什么是分区二、有什么作用三、分类四、创建分区五、删除分区 一、什么是分区 MySQL 分区(Partitioning)是一种将单张表的数据逻辑上拆分成多个物理部分的技术。这些物理部分(分区)可以独立存储、管理和优化,…...
「全栈技术解析」推客小程序系统开发:从架构设计到裂变增长的完整解决方案
在移动互联网营销竞争白热化的当下,推客小程序系统凭借其裂变传播、精准营销等特性,成为企业抢占市场的利器。本文将深度解析推客小程序系统开发的核心技术与实现路径,助力开发者打造具有市场竞争力的营销工具。 一、系统核心功能架构&…...
