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

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 坐标轴上&#xff0c;有许多水果分布在其中某些位置。给你一个二维整数数组 fruits &#xff0c;其中 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)

互联网摸鱼日报&#xff08;2023-05-09&#xff09; InfoQ 热门话题 面向数字化提质提效的低代码架构设计 | 低代码技术内幕 提升字节规模化效能的平台化思路 &#xff5c; 极客有约 从微服务转为单体架构、成本降低 90%&#xff0c;亚马逊内部案例引发轰动&#xff01;CTO&…...

MySQL常见的存储引擎

InnoDB&#xff1a;InnoDB是一种兼顾高可靠性和高性能的通用存储引擎&#xff0c;在MySQL 5.5之后&#xff0c;InnoDB是默认的MySQL存储引擎。 特点&#xff1a;1、DML操作遵循ACID模型&#xff0c;支持事务; 2、行级锁&#xff0c;提高并发访问性能; 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 控制台&#xff0c; “ /home/ssh/openssh-4.6p1” 目录下&#xff0c; 使用命 令“ssh-keygen -t rsa -f ssh…...

常见舆情监测系统的分类和特点

随着网络和社交媒体的发展&#xff0c;舆情监测系统逐渐成为企业和政府机构必备的工具之一。舆情监测系统可以帮助企业和政府机构全面了解公众对其品牌、产品、政策等的反应和态度&#xff0c;及时发现和解决问题&#xff0c;提高公信力和形象。本文将介绍常见的舆情监测系统的…...

联合群美叶彦文:坚持,只要有一口气,能坚持多久,就坚持多久

创业之路的成败得失就看有多坚持。 成功并不是终点&#xff0c;失败并不是终结&#xff0c;只有勇气才是永恒。 Success is not final,failure is not fatal,it is the courage to continue that counts. ——温斯顿丘吉尔 迪斯雷利曾经说过&#xff1a;“成功的奥秘在于目标…...

动态规划的学习

文章目录 动态规划的学习一、什么是动态规划&#xff1f;二、如何思考状态转移方程&#xff1f;三、动态规划的基本原理1.[509. 斐波那契数](https://leetcode.cn/problems/fibonacci-number/)1.1 暴力递归解法&#xff1a;1.1.1 递归算法的时间复杂度那为什么时间复杂度会这么…...

计算机网络:HTTPS

目录 HTTP 与 HTTPS 有哪些区别&#xff1f;HTTPS 解决了 HTTP 的哪些问题HTTPS 是如何建立连接的&#xff1f;其间交互了什么TLS 协议建立的详细流程客户端校验数字证书的流程是怎样的&#xff1f; HTTPS 的应用数据是如何保证完整性的HTTPS 一定安全可靠吗参考资料 HTTP 与 H…...

数据库系列-什么是 JDBC?它的作用是什么?

JDBC&#xff08;Java Database Connectivity&#xff09;是 Java 语言提供的一种访问数据库的标准接口&#xff0c;它定义了一组 Java 接口和类&#xff0c;用于实现 Java 程序与各种关系型数据库的连接和交互。JDBC 的主要作用是提供了一种标准的、可靠的、跨平台的方式来访问…...

C++学习day--08 数组和字符串

1、什么是数组 数组&#xff0c;就是多个元素的有序“组合”。 C 和 C语言中的数组&#xff1a; 1 &#xff09;由多个大小相同的小柜子组成 > 相同大小的内存块组成&#xff0c;即相同类型的数据 2 &#xff09;这些小柜子&#xff0c;有自己对应的编号 > 编号从 …...

系统分析师之系统测试与维护(十六)

目录 一、 测试与评审 1.1 测试类型 1.2 测试阶段 1.3 面向对象的测试 1.4 测试自动化 1.5 软件调试 1.6 软件评审 1.7 验收与确认 二、软件质量管理 2.1 软件过程改进-CMMI 2.2 软件开发环境与工具 三、系统运行与评价 3.1 系统转换计划 3.1.1 遗留系统演化策略…...

板材激光切割机切割穿孔时注意的几个问题

激光切割设备广泛应用于钣金、五金制品、钢结构、汽车配件、广告、工艺品等行业&#xff0c;成为加工行业不可缺少的环节。在厚板加工中穿孔时间占很大比重&#xff0c;随着加工板材越来越厚&#xff0c;板材激光切割机切割穿孔也会相应地增加难度。 激光切割机两种常见的穿孔方…...

奶爸式Swagger教学

目录 一、导入依赖 二、SwaggerConfig基础编程 三、Swagger 常用说明注解 1.API 2.ApiOperation 3.ApiModel 4.ApiModelProperty 5.ApiParam 6.ApilmplicitParam 一、导入依赖 <!--开启Swagger --><!-- https://mvnrepository.com/artifact/io.springf…...

入门级的家用洗地机怎么样?入门级洗地机推荐

洗地机的功能有很多&#xff0c;比如除菌、洗地机清洁地面的确是一把好手。但是&#xff01;清洁完之后还要手动清洗洗地机&#xff0c;是一件麻烦事啊&#xff01;现在市面上大部分洗地机都有自清洁这个功能&#xff0c;但是很多洗地机的自清洁并不算真正的自清洁&#xff0c;…...

【面试】Java 反射机制(常见面试题)

文章目录 前言一、反射是什么&#xff1f;二、为什么要有反射三、反射 API3.1 获取 Class 对象的三种方式3.2 获取成员变量3.3 获取构造方法3.4.获取非构造方法 四、实践五、常见面试题5.1. 什么是反射&#xff1f;5.2. 哪里用到反射机制&#xff1f;5.3. 什么叫对象序列化&…...

JavaScript最佳实践

JavaScript最佳实践 2023.5.8版权声明&#xff1a;本文为博主chszs的原创文章&#xff0c;未经博主允许不得转载。 JavaScript 是一种动态编程语言&#xff0c;可让开发者创建动态和交互式 Web 应用程序。然而&#xff0c;编写 JavaScript 代码比较具有挑战性&#xff0c;尤其…...

景23转债,海能转债上市价格预测

景23转债 基本信息 转债名称&#xff1a;景23转债&#xff0c;评级&#xff1a;AA&#xff0c;发行规模&#xff1a;11.54亿元。 正股名称&#xff1a;景旺电子&#xff0c;今日收盘价&#xff1a;22.52元&#xff0c;转股价格&#xff1a;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虽…...

wordpress后台更新后 前端没变化的解决方法

使用siteground主机的wordpress网站&#xff0c;会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后&#xff0c;网站没有变化的情况。 不熟悉siteground主机的新手&#xff0c;遇到这个问题&#xff0c;就很抓狂&#xff0c;明明是哪都没操作错误&#x…...

多模态2025:技术路线“神仙打架”,视频生成冲上云霄

文&#xff5c;魏琳华 编&#xff5c;王一粟 一场大会&#xff0c;聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中&#xff0c;汇集了学界、创业公司和大厂等三方的热门选手&#xff0c;关于多模态的集中讨论达到了前所未有的热度。其中&#xff0c;…...

Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误

HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误&#xff0c;它们的含义、原因和解决方法都有显著区别。以下是详细对比&#xff1a; 1. HTTP 406 (Not Acceptable) 含义&#xff1a; 客户端请求的内容类型与服务器支持的内容类型不匹…...

【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器

一.自适应梯度算法Adagrad概述 Adagrad&#xff08;Adaptive Gradient Algorithm&#xff09;是一种自适应学习率的优化算法&#xff0c;由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率&#xff0c;适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...

React Native 开发环境搭建(全平台详解)

React Native 开发环境搭建&#xff08;全平台详解&#xff09; 在开始使用 React Native 开发移动应用之前&#xff0c;正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南&#xff0c;涵盖 macOS 和 Windows 平台的配置步骤&#xff0c;如何在 Android 和 iOS…...

java 实现excel文件转pdf | 无水印 | 无限制

文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...

解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八

现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet&#xff0c;点击确认后如下提示 最终上报fail 解决方法 内核升级导致&#xff0c;需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...

C# 类和继承(抽象类)

抽象类 抽象类是指设计为被继承的类。抽象类只能被用作其他类的基类。 不能创建抽象类的实例。抽象类使用abstract修饰符声明。 抽象类可以包含抽象成员或普通的非抽象成员。抽象类的成员可以是抽象成员和普通带 实现的成员的任意组合。抽象类自己可以派生自另一个抽象类。例…...

CRMEB 中 PHP 短信扩展开发:涵盖一号通、阿里云、腾讯云、创蓝

目前已有一号通短信、阿里云短信、腾讯云短信扩展 扩展入口文件 文件目录 crmeb\services\sms\Sms.php 默认驱动类型为&#xff1a;一号通 namespace crmeb\services\sms;use crmeb\basic\BaseManager; use crmeb\services\AccessTokenServeService; use crmeb\services\sms\…...

【Kafka】Kafka从入门到实战:构建高吞吐量分布式消息系统

Kafka从入门到实战:构建高吞吐量分布式消息系统 一、Kafka概述 Apache Kafka是一个分布式流处理平台,最初由LinkedIn开发,后成为Apache顶级项目。它被设计用于高吞吐量、低延迟的消息处理,能够处理来自多个生产者的海量数据,并将这些数据实时传递给消费者。 Kafka核心特…...