2023-05-04 LeetCode每日一题(摘水果)
2023-05-04每日一题
一、题目编号
2106. 摘水果
二、题目链接
点击跳转到题目位置
三、题目描述
在一个无限的 x 坐标轴上,有许多水果分布在其中某些位置。给你一个二维整数数组 fruits ,其中 fruits[i] = [positioni, amounti] 表示共有 amounti 个水果放置在 positioni 上。fruits 已经按 positioni 升序排列 ,每个 positioni 互不相同 。
另给你两个整数 startPos 和 k 。最初,你位于 startPos 。从任何位置,你可以选择 向左或者向右 走。在 x 轴上每移动 一个单位 ,就记作 一步 。你总共可以走 最多 k 步。你每达到一个位置,都会摘掉全部的水果,水果也将从该位置消失(不会再生)。
返回你可以摘到水果的 最大总数 。
四、解题代码
class Solution {
public:int maxTotalFruits(vector<vector<int>>& fruits, int startPos, int k) {int n = fruits.size();long long sum[400010];memset(sum, 0, sizeof(sum));for(int i = 0; i < n; ++i){sum[fruits[i][0]] = fruits[i][1]; }for(int i = 1; i <= 200000; ++i){sum[i] += sum[i-1];}if(startPos == 0){return sum[min(200000, k)];}long long max0 = 0;for(int i = 0; i <= k; ++i){if(i == startPos){max0 = max(max0 ,sum[max(startPos, startPos - 2 * i + k)]);} else if(i < startPos){max0 = max(max0, sum[max(startPos, startPos - 2 * i + k )] - sum[startPos - i - 1]);}if(startPos + i <= 200000){if(max(k - 2 * i, 0) >= startPos){max0 = max(sum[startPos + i], max0);} else{max0 = max(max0, sum[startPos + i] - sum[startPos - max(k - 2 * i, 0) - 1]); }}}return max0;}
};
五、解题思路
(1) 首先我们思考能走多少步,设步数为i。我们很容易可以根据题目来知晓,这个步数为0 ~ k。
(2) 那我们将问题转化成,我们该如何规划这i步,使得摘到的水果最多。我们根据贪心的原理可以很容易知晓,我们应该尽可能的利用上我们的步数。那么我们的问题就转化成一开始是往右走,还是一开始往左走。
(3) 这样我们可以根据往左走或者往右走的步数,规划出一个窗口。计算出该窗口中水果的数目,只要取水果数目最大的窗口即为最终的答案。
(4) 最后我们只需要用前缀和来求出遍历到的每一个窗口中水果的数目即可。
相关文章:
2023-05-04 LeetCode每日一题(摘水果)
2023-05-04每日一题 一、题目编号 2106. 摘水果二、题目链接 点击跳转到题目位置 三、题目描述 在一个无限的 x 坐标轴上,有许多水果分布在其中某些位置。给你一个二维整数数组 fruits ,其中 fruits[i] [positioni, amounti] 表示共有 amounti 个水…...
[工具]Pytorch-lightning的使用
Pytorch-lightning的使用 Pytorch-lightning介绍Pytorch-lightning与Pytorch的区别Pytorch-lightning框架的优势Pytorch-lightning框架 重要资源 Pytorch-lightning介绍 这里介绍Pytorch_lighting框架. Pytorch-lightning与Pytorch的区别 Pytorch-lightning可以简单的看作是…...
互联网摸鱼日报(2023-05-09)
互联网摸鱼日报(2023-05-09) InfoQ 热门话题 面向数字化提质提效的低代码架构设计 | 低代码技术内幕 提升字节规模化效能的平台化思路 | 极客有约 从微服务转为单体架构、成本降低 90%,亚马逊内部案例引发轰动!CTO&…...
MySQL常见的存储引擎
InnoDB:InnoDB是一种兼顾高可靠性和高性能的通用存储引擎,在MySQL 5.5之后,InnoDB是默认的MySQL存储引擎。 特点:1、DML操作遵循ACID模型,支持事务; 2、行级锁,提高并发访问性能; 3、支持外键FOREIGN KEY约…...
迅为i.MX6ULL开发板生成 KEY 文件,并安装
使用“ssh-keygen” 生成个四个 key 文件“ssh_host_rsa_key” “ssh_host_dsa_key” “ssh_host_ecdsa_key” 和“ssh_host_ed25519_key” 。 1 在虚拟机 Ubuntu 控制台, “ /home/ssh/openssh-4.6p1” 目录下, 使用命 令“ssh-keygen -t rsa -f ssh…...
常见舆情监测系统的分类和特点
随着网络和社交媒体的发展,舆情监测系统逐渐成为企业和政府机构必备的工具之一。舆情监测系统可以帮助企业和政府机构全面了解公众对其品牌、产品、政策等的反应和态度,及时发现和解决问题,提高公信力和形象。本文将介绍常见的舆情监测系统的…...
联合群美叶彦文:坚持,只要有一口气,能坚持多久,就坚持多久
创业之路的成败得失就看有多坚持。 成功并不是终点,失败并不是终结,只有勇气才是永恒。 Success is not final,failure is not fatal,it is the courage to continue that counts. ——温斯顿丘吉尔 迪斯雷利曾经说过:“成功的奥秘在于目标…...
动态规划的学习
文章目录 动态规划的学习一、什么是动态规划?二、如何思考状态转移方程?三、动态规划的基本原理1.[509. 斐波那契数](https://leetcode.cn/problems/fibonacci-number/)1.1 暴力递归解法:1.1.1 递归算法的时间复杂度那为什么时间复杂度会这么…...
计算机网络:HTTPS
目录 HTTP 与 HTTPS 有哪些区别?HTTPS 解决了 HTTP 的哪些问题HTTPS 是如何建立连接的?其间交互了什么TLS 协议建立的详细流程客户端校验数字证书的流程是怎样的? HTTPS 的应用数据是如何保证完整性的HTTPS 一定安全可靠吗参考资料 HTTP 与 H…...
数据库系列-什么是 JDBC?它的作用是什么?
JDBC(Java Database Connectivity)是 Java 语言提供的一种访问数据库的标准接口,它定义了一组 Java 接口和类,用于实现 Java 程序与各种关系型数据库的连接和交互。JDBC 的主要作用是提供了一种标准的、可靠的、跨平台的方式来访问…...
C++学习day--08 数组和字符串
1、什么是数组 数组,就是多个元素的有序“组合”。 C 和 C语言中的数组: 1 )由多个大小相同的小柜子组成 > 相同大小的内存块组成,即相同类型的数据 2 )这些小柜子,有自己对应的编号 > 编号从 …...
系统分析师之系统测试与维护(十六)
目录 一、 测试与评审 1.1 测试类型 1.2 测试阶段 1.3 面向对象的测试 1.4 测试自动化 1.5 软件调试 1.6 软件评审 1.7 验收与确认 二、软件质量管理 2.1 软件过程改进-CMMI 2.2 软件开发环境与工具 三、系统运行与评价 3.1 系统转换计划 3.1.1 遗留系统演化策略…...
板材激光切割机切割穿孔时注意的几个问题
激光切割设备广泛应用于钣金、五金制品、钢结构、汽车配件、广告、工艺品等行业,成为加工行业不可缺少的环节。在厚板加工中穿孔时间占很大比重,随着加工板材越来越厚,板材激光切割机切割穿孔也会相应地增加难度。 激光切割机两种常见的穿孔方…...
奶爸式Swagger教学
目录 一、导入依赖 二、SwaggerConfig基础编程 三、Swagger 常用说明注解 1.API 2.ApiOperation 3.ApiModel 4.ApiModelProperty 5.ApiParam 6.ApilmplicitParam 一、导入依赖 <!--开启Swagger --><!-- https://mvnrepository.com/artifact/io.springf…...
入门级的家用洗地机怎么样?入门级洗地机推荐
洗地机的功能有很多,比如除菌、洗地机清洁地面的确是一把好手。但是!清洁完之后还要手动清洗洗地机,是一件麻烦事啊!现在市面上大部分洗地机都有自清洁这个功能,但是很多洗地机的自清洁并不算真正的自清洁,…...
【面试】Java 反射机制(常见面试题)
文章目录 前言一、反射是什么?二、为什么要有反射三、反射 API3.1 获取 Class 对象的三种方式3.2 获取成员变量3.3 获取构造方法3.4.获取非构造方法 四、实践五、常见面试题5.1. 什么是反射?5.2. 哪里用到反射机制?5.3. 什么叫对象序列化&…...
JavaScript最佳实践
JavaScript最佳实践 2023.5.8版权声明:本文为博主chszs的原创文章,未经博主允许不得转载。 JavaScript 是一种动态编程语言,可让开发者创建动态和交互式 Web 应用程序。然而,编写 JavaScript 代码比较具有挑战性,尤其…...
景23转债,海能转债上市价格预测
景23转债 基本信息 转债名称:景23转债,评级:AA,发行规模:11.54亿元。 正股名称:景旺电子,今日收盘价:22.52元,转股价格:25.71元。 当前转股价值 转债面值 / …...
TDengine 部署与使用----时序数据库
官网 通过 Docker 快速体验 TDengine | TDengine 文档 | 涛思数据 docker安装 拉取最新docker镜像 docker pull tdengine/tdengine:latest 然后执行 docker run -d -p 6030:6030 -p 6041:6041 -p 6043-6049:6043-6049 -p 6043-6049:6043-6049/udp tdengine/tdengine 查看容器…...
ShardingSphere系列四(Sharding-JDBC内核原理及核心源码解析)
文章目录 1. ShardingSphere内核解析1.1 解析引擎1.2 路由引擎1.3 改写引擎1.4 执行引擎1.5 归并引擎 2. ShardingSphere的SPI扩展点2.1 SPI机制2.2 ShardingSphere中的SPI扩展点2.3 实现自定义主键生成策略 3. ShardingSphere源码 1. ShardingSphere内核解析 ShardingSphere虽…...
python打卡day49
知识点回顾: 通道注意力模块复习空间注意力模块CBAM的定义 作业:尝试对今天的模型检查参数数目,并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...
阿里云ACP云计算备考笔记 (5)——弹性伸缩
目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...
Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件
今天呢,博主的学习进度也是步入了Java Mybatis 框架,目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学,希望能对大家有所帮助,也特别欢迎大家指点不足之处,小生很乐意接受正确的建议&…...
Linux简单的操作
ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...
多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验
一、多模态商品数据接口的技术架构 (一)多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如,当用户上传一张“蓝色连衣裙”的图片时,接口可自动提取图像中的颜色(RGB值&…...
postgresql|数据库|只读用户的创建和删除(备忘)
CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...
unix/linux,sudo,其发展历程详细时间线、由来、历史背景
sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...
Angular微前端架构:Module Federation + ngx-build-plus (Webpack)
以下是一个完整的 Angular 微前端示例,其中使用的是 Module Federation 和 npx-build-plus 实现了主应用(Shell)与子应用(Remote)的集成。 🛠️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...
Xen Server服务器释放磁盘空间
disk.sh #!/bin/bashcd /run/sr-mount/e54f0646-ae11-0457-b64f-eba4673b824c # 全部虚拟机物理磁盘文件存储 a$(ls -l | awk {print $NF} | cut -d. -f1) # 使用中的虚拟机物理磁盘文件 b$(xe vm-disk-list --multiple | grep uuid | awk {print $NF})printf "%s\n"…...
在QWebEngineView上实现鼠标、触摸等事件捕获的解决方案
这个问题我看其他博主也写了,要么要会员、要么写的乱七八糟。这里我整理一下,把问题说清楚并且给出代码,拿去用就行,照着葫芦画瓢。 问题 在继承QWebEngineView后,重写mousePressEvent或event函数无法捕获鼠标按下事…...
