【LeetCode刷题-滑动窗口】--1658.将x减到0的最小操作数

1658.将x减到0的最小操作数

image-20231115223334607

思路与算法:

根据题目描述,在每一次操作中,可以移除数组nums最左边和最右边的元素,因此,在所有的操作完成后,数组nums的一个前缀以及一个后缀被移除,并且它们的和恰好为x,前缀 以及后缀可以为空

记数组的长度为n,可以用left和right分别表示选择的前缀以及后缀的边界,如果left=-1,表示选择了空前缀;如果right=n表示我们选择了空后缀

由于数组nums中的元素均为正数,因此当left向右移动(即前缀的范围增加)时,它们的和是严格递增的,要想将它们的和控制在x,必须将right向右移动,可以用滑动窗口的方法来解决

初始时,left的值为-1,right为0,表示选择了空前缀以及整个数组作为后缀,用lsum和rsum分别记录前缀以及后缀的和,那么:

  • 如果lsum + rsum = x,说明我们找到了一组答案,对应的操作次数为(left+1)+(n-right)
  • 如果lsum + rsum > x,说明和过大,需要将right向右移动一个位置
  • 如果lsum + rsum < x,说明和过小,需要将left向右移动一个位置
class Solution {public int minOperations(int[] nums, int x) {int n = nums.length;int sum = Arrays.stream(nums).sum();  //数组总和if(sum < x){return -1;}//left和right为选择的前缀和后缀的边界int right = 0;int lsum = 0,rsum = sum;  //lsum和rsum分别表示前缀和和后缀和int ans = n + 1;for(int left = -1 ; left < n ; left++){  if(left != -1){   lsum += nums[left]; }while(right < n && lsum + rsum > x){  //和过大,需要将right向右移动一个位置rsum -= nums[right]; ++right;}if(lsum + rsum == x){  ans = Math.min(ans,(left + 1) + (n - right));  }}return ans > n ? -1:ans;}
}

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

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

相关文章

拿走吧你,Fiddler模拟请求发送和修改响应数据

fiddler模拟伪造请求 方法一&#xff1a;打断点模拟HTTP请求 1、浏览器页面填好内容后&#xff08;不要操作提交&#xff09;&#xff0c;打开fiddler&#xff0c;设置请求前断点&#xff0c;点击菜单fiddler,”Rules”\”Automatic Breakpoints”\”Before Requests” 2、在…

PDF文件标题修改方法

目录 一、PDF文件的标题和名称 二、标题修改方法 1.浏览器打开PDF Editor Free网站 2.点击Free Oline 3.选择第三个从本地上传PDF附件 4.将附件上传&#xff0c;两种方法都可以​编辑 5.等待加载&#xff0c;附件大的情况下会有些慢&#xff0c;耐心等待即可 6. 导入文…

在windows下vs c++运行g2o的BA优化程序示例

目录 1、前言2、准备工作安装git安装vcpkg&#xff08;1&#xff09;下载&#xff08;2&#xff09;安装&#xff08;3&#xff09;集成至vs 安装cmake 3、安装g2o4、安装opencv&#xff08;1&#xff09;下载&#xff08;2&#xff09;双击安装&#xff08;3&#xff09;环境变…

git clone:SSL: no alternative certificate subject name matches target host name

git clone 时的常见错误&#xff1a; fatal: unable to access ‘https://ip_or_domain/xx/xx.git/’: SSL: no alternative certificate subject name matches target host name ‘ip_or_domain’ 解决办法&#xff1a; disable ssl verify git config --global http.sslVe…

软件自动化测试作用简析,为什么要选择第三方软件测评机构?

软件自动化测试是把以人为驱动的测试行为转化为机器执行的一种过程。通常&#xff0c;在设计了测试用例并通过评审之后&#xff0c;由测试人员根据测试用例中描述的规程一步步执行测试&#xff0c;得到实际结果与期望结果的比较。 一、自动化测试的作用   1.测试效能大幅度提…

一起学docker系列之二深入理解Docker:基本概念、工作原理与架构

目录 前言1 Docker的基本概念2 Docker的基本组成3 docker工作原理4 docker架构5 Docker详细工作过程结语 前言 在当今的软件开发和部署中&#xff0c;Docker已经成为一种不可或缺的工具。它简化了应用程序的打包、交付和运行&#xff0c;同时提供了强大的隔离性和可移植性。本…

安科瑞为数据中心绿色高质量发展贡献力量

安科瑞 崔丽洁  0前言 目前&#xff0c;数字经济的迅猛发展激发了数据中心的算力需求&#xff0c;数据中心规模与功耗密度不断提高&#xff0c;能耗问题日益突出。短期内&#xff0c;数据中心的能耗、碳排放量仍会呈现上升趋势。面对国家“双碳”压力&#xff0c;我国数据中心…

mysql之搭建MMM架构实现高可用

实验目的 解决mysql的主从服务器单点故障问题&#xff0c;实现高可用 实验思路 实验条件&#xff1a; 主机名 作用 IP地址 组件 mysql1 master01 20.0.0.13 mysql服务、mysql-mmm mysql2 masert02 20.0.0.23 mysql服务、mysql-mmm mysql3 slave01 20.0.0.33 …

关于Flume-Kafka-Flume的模式进行数据采集操作

测试是否连接成功&#xff1a; 在主节点flume目录下输入命令: bin/flume-ng agent -n a1 -c conf/ -f job/file_to_kafka.conf -Dflume.root.loggerinfo,console # 这个file_to_kafka.conf文件就是我们的配置文件 然后在另一台节点输入命令进行消费数据&#xff1a; kafka-cons…

三菱FX3U小项目—机床定时器延时启动

目录 一、项目描述 二、IO口分配 三、项目程序 四、总结 一、项目描述 为了防止工人操作失误&#xff0c;启动按钮需要按住1s后&#xff0c;设备才启动&#xff0c;启动后第一台电机启动10s后第二台电机自动启动&#xff0c;当按下停止按钮时&#xff0c;两台电机同时停止。…

Django部署时静态文件配置的坑

Django部署时静态文件配置配置的坑 近期有个需求是用django进行开发部署&#xff0c;结果发现静态文件配置的坑是真的多&#xff0c;另外网上很多的内容也讲不清楚原理&#xff0c;就是这样这样&#xff0c;又那样那样&#xff0c;进了不少坑&#xff0c;这里记录一下关于css,…

【Apache Doris】审计日志插件 | 快速体验

【Apache Doris】审计日志插件 | 快速体验 一、 环境信息1.1 硬件信息1.2 软件信息 二、 审计日志插件介绍三、 快速 体验3.1 AuditLoader 配置3.1.1 下载 Audit Loader 插件3.1.2 解压安装包3.1.3 修改 plugin.conf 3.2 创建库表3.3 初始化3.4 验证 一、 环境信息 1.1 硬件信…

windiws docker 部署jar window部署docker 转载

Windows环境下从安装docker到部署前后端分离项目(springboot+vue) 一、前期准备 1.1所需工具: 1.2docker desktop 安装 二、部署springboot后端项目 2.1 部署流程 三、部署vue前端项目 3.1相关条件 3.2部署流程 四、前后端网络请求测试 一、前期准备 1.1所需工具: ①docke…

小米手环8pro重新和手机配对解决办法

如果更换了手机&#xff0c;那么小米手环8pro是无法和新手机自动连接的。 但是在新手机上直接连接又连接不上&#xff0c;搜索蓝牙根本找不到手环的蓝牙。 解决办法就是&#xff1a; 把手环恢复出厂&#xff01;&#xff01;&#xff01;&#xff01;&#xff01; 是的&…

苹果MAC安装绿盾出现问题,安装时没有出现填服务器地址的页面,现在更改不了也卸载不了绿盾 怎么处理?

环境: Mac mini M1 Mac os 11.0 绿盾v6.5 问题描述: 苹果MAC安装绿盾出现问题,安装时没有出现填服务器地址的页面,现在更改不了也卸载不了绿盾 怎么处理? 解决方案: 大部分企业是Windows和Mac终端混合使用,在进行文档加密管理时通常会遇到不兼容的现象,而为了统一…

Scala---数据基础

一、数据类型 二、变量和常量的声明 定义变量或者常量的时候&#xff0c;也可以写上返回的类型&#xff0c;一般省略&#xff0c;如&#xff1a;val a:Int 10常量不可再赋值 1./** 2. * 定义变量和常量 3. * 变量 :用 var 定义 &#xff0c;可修改 4. * 常量 :用 val 定…

基于IGT-DSER实现工业触摸屏与PLC设备之间WIFI无线通讯

本文是基于IGT-DSER系列智能网关设备实现工业触摸屏与PLC设备之间WIFI无线通讯的案例。PLC之间无线通讯的案例 网络结构如下图&#xff0c;触摸屏通过网线连接IGT-DSERWIFI智能网关&#xff0c;实现WIFI的AP功能&#xff1b;一台串口型PLC和一台网口型PLC分别通过IGT-WSER智能网…

数据同步工具调研选型:SeaTunnel 与 DataX 、Sqoop、Flume、Flink CDC 对比

产品概述 Apache SeaTunnel 是一个非常易用的超高性能分布式数据集成产品&#xff0c;支持海量数据的离线及实时同步。每天可稳定高效同步万亿级数据&#xff0c;已应用于数百家企业生产&#xff0c;也是首个由国人主导贡献到 Apache 基金会的数据集成顶级项目。 SeaTunnel 主…

2023数维杯国际赛数学建模竞赛选题建议及B题思路讲解

大家好呀&#xff0c;2023年第九届数维杯国际大学生数学建模挑战赛今天早上开赛啦&#xff0c;在这里先带来初步的选题建议及思路。 目前团队正在写B题和D题完整论文&#xff0c;后续还会持续更新哈&#xff0c;大家三连关注一下防止迷路。 注意&#xff0c;本文只是比较简略…

【Linux系统化学习】探索进程的奥秘 | 第一个系统调用

个人主页点击直达&#xff1a;小白不是程序媛 Linux系列专栏&#xff1a;系统化学习Linux 目录 进程的概念 进程的管理 描述进程——pcb 组织进程 进程在排队 Linux下的进程 Linux组织进程 查看进程 查看可执行程序的进程 第一个系统调用 "杀掉进程" 进程…