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

滑动窗口实例4(将x减到0的最小操作数)

题目:

给你一个整数数组 nums 和一个整数 x 。每一次操作时,你应当移除数组 nums 最左边或最右边的元素,然后从 x 中减去该元素的值。请注意,需要 修改 数组以供接下来的操作使用。

如果可以将 x 恰好 减到 0 ,返回 最小操作数 ;否则,返回 -1 。

示例 1:

输入:nums = [1,1,4,2,3], x = 5
输出:2
解释:最佳解决方案是移除后两个元素,将 x 减到 0 。

示例 2:

输入:nums = [5,6,7,8,9], x = 4
输出:-1

示例 3:

输入:nums = [3,2,20,1,1,3], x = 10
输出:5
解释:最佳解决方案是移除后三个元素和前两个元素(总共 5 次操作),将 x 减到 0 。

提示:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 104
  • 1 <= x <= 109

算法原理:

正面入手解题,情况繁杂,一会是取左边一会是取右边,但是正难则反,反面入手解题:

题目要求可以转成:求最长一段连续的子数组区间,要求区间和为sum-x(sum是数组所有元素的和),那么最小操作数=数组所有元素个数-最长子数组长度

题目本来的要求是:求「左端+右端」两段连续的、和为 x 的最短数组

连续区间,可以考虑用滑动窗口来解题

1 求出数组所有元素的和sum 目标值target=sum-x

2 用滑动窗口,找出最长的子数组,使其和为target

   细节:target可能为负数(当sum<x时)但是题目提示中所有元素均不存在负数

             所以返回-1

   left=0(左边界) right=0(指向待进入窗口的元素) sum2统计区间和

   a 进窗口:sum2+=nums[right] 

   b 判断:    若是sum2>target 循环出窗口,直至sum<=target

                     若是循环结束后,sum2==target,则找到一组结果,若此次结果更优则更新结果

   c 出窗口:sum-=nums[left],left++

代码实现:

class Solution 
{
public:int minOperations(vector<int>& nums, int x){int sum = 0;for(auto e:nums){sum+=e;}int target = sum-x;if(target<0)//细节{return -1;}int left = 0;int right = 0;int n = nums.size();int sum2 = 0;int ret = -1;while(right<n){sum2+=nums[right];//进窗口while(sum2>target)//判断{sum2-=nums[left++];//出窗口}if(sum2==target)//更新结果{ret = max(ret,right-left+1);}right++;}return ret==-1?ret: n-ret;}
};

相关文章:

滑动窗口实例4(将x减到0的最小操作数)

题目&#xff1a; 给你一个整数数组 nums 和一个整数 x 。每一次操作时&#xff0c;你应当移除数组 nums 最左边或最右边的元素&#xff0c;然后从 x 中减去该元素的值。请注意&#xff0c;需要 修改 数组以供接下来的操作使用。 如果可以将 x 恰好 减到 0 &#xff0c;返回 …...

数据库原理及应用(MySQL)

建议大屏观看&#xff0c;避免格式错误&#xff0c;影响观感 目录 第一章 数据库系统概述 1.数据库系统概述 1.1.信息 1.2.数据 1.3.信息和数据之间的联系 1.4.数据库&#xff08;DB&#xff09; 1.5.数据库管理系统&#xff08;DBMS&#xff09; 1.6.数据库管理系统的…...

初识Maven(一)命令行操作和idea创建maven工程

Maven 是 Apache 软件基金会组织维护的一款专门为 Java 项目提供**构建**和**依赖**管理支持的工具。 构建过程包含的主要的环节&#xff1a;- 清理&#xff1a;删除上一次构建的结果&#xff0c;为下一次构建做好准备 - 编译&#xff1a;Java 源程序编译成 *.class 字节码文件…...

MHA高可用配置及故障切换

1&#xff0e;什么是 MHA MHA&#xff08;MasterHigh Availability&#xff09;是一套优秀的MySQL高可用环境下故障切换和主从复制的软件。 MHA 的出现就是解决MySQL 单点的问题。 MySQL故障切换过程中&#xff0c;MHA能做到0-30秒内自动完成故障切换操作。 MHA能在故障切换的过…...

FPGA/IC秋招面试题 1(解析版)

分享个人觉得遇到还不错的题&#xff0c;后续有会继续补充。。。 以下题目均来自网络平台&#xff0c;用于学习交流如有侵权立马删除!!! 1. Verilog语言中&#xff0c;下面哪些语句不可被综合() A. #delay语句 B. initial语句 C. always语句 D. 用gen…...

华为云 异构数据迁移

数据库和应用迁移 UGO&#xff08;Database and Application Migration UGO&#xff0c;以下简称为UGO&#xff09;是专注于异构数据库结构迁移的专业服务。可将源数据库中的DDL、DML和DCL一键自动转换为华为云GaussDB/RDS的SQL语法&#xff0c;通过数据库评估、对象迁移两大核…...

wininet,winhttp,xmlhttprequest,各版本区别 《转》

一、标准API接口WinINet(Microsoft Windows Internet)和WinHTTP(Microsoft Windows HTTP) 实现Http访问&#xff0c;微软提供了二套API&#xff1a;WinINet, WinHTTP&#xff08;分别封装于system32目录下的wininet.dll和winhttp.dll内&#xff09; 二者主要区别在于后者更为安…...

朴素,word,任何参考文献导入endnote

朴素&#xff0c;word&#xff0c;任何参考文献导入endnote 注意&#xff1a;对于以下这几种不做阐述&#xff0c;看其他帖子都有讲述&#xff1a; 这里的参考文献指的是类似于&#xff1a; [1]. Li Y, Lu Y, Huo X, et al. Bandgap tuning strategy by cations and halide io…...

数学建模--三维图像绘制的Python实现

目录 1.绘制三维坐标轴的方法 2.绘制三维函数的样例1 3.绘制三维函数的样例2 4.绘制三维函数的样例3 5.绘制三维函数的样例4 6.绘制三维函数的样例5 1.绘制三维坐标轴的方法 #%% #1.绘制三维坐标轴的方法 from matplotlib import pyplot as plt from mpl_toolkits.mplot3…...

Spring Cloud Alibaba-Feign整合Sentinel

第1步: 引入sentinel的依赖 <!--sentinel客户端--> <dependency><groupId>com.alibaba.cloud</groupId><artifactId>spring-cloud-starter-alibaba-sentinel</artifactId> </dependency> 第2步: 在配置文件中开启Feign对Sentinel的…...

zabbix配置钉钉告警、和故障自愈

钉钉告警python脚本 cat python20 #!/usr/bin/python3 #coding:utf-8 import requests,json,sys,os,datetime # 机器人的Webhook地址 webhook"钉钉" usersys.argv[1] textsys.argv[3] data{"msgtype": "text","text": {"conten…...

Web安全测试(五):XSS攻击—存储式XSS漏洞

一、前言 结合内部资料,与安全渗透部门同事合力整理的安全测试相关资料教程,全方位涵盖电商、支付、金融、网络、数据库等领域的安全测试,覆盖Web、APP、中间件、内外网、Linux、Windows多个平台。学完后一定能成为安全大佬! 全部文章请访问专栏:《全栈安全测试教程(0基…...

本地PC机通过SSH方式远程Jetson

1. 检测电脑是否安装openSSH 以管理员身份运行powershell终端输入以下命令&#xff1a; Get-WindowsCapability -Online | ? Name -like OpenSSH*若没有安装OpenSSH&#xff0c;会出现如下图提示&#xff1a; 输入Add-WindowsCapability -Online -Name OpenSSH.Client~~~~0.…...

面向对象 学习黑马视频(03)

1.内存分区模型 /* 面向对象编程** 内存分区模型* 1.代码区&#xff1a;存放函数体的二进制代码&#xff0c;由操作系统进行管理的* 2.全局区&#xff1a;存放全局变量和静态变量以及常量* 3.栈区&#xff1a;由编译器自动分配释放&#xff0c;存放函数的参数值…...

FinClip 支持创建 H5应用类小程序;PC 终端 优化升级

FinClip 的使命是使您能够通过小程序解决关键业务流程挑战&#xff0c;并完成数字化转型。不妨让我们看看本月产品与市场发布亮点&#xff0c;是否有助于您实现目标。 产品方面的相关动向&#x1f447;&#x1f447;&#x1f447; FinClip 支持创建 H5应用类小程序 近期我们…...

YOLOV8实例分割——详细记录环境配置、自定义数据处理到模型训练与部署

前言 Ultralytics YOLOv8是一种前沿的、最先进的&#xff08;SOTA&#xff09;模型&#xff0c;它在前代YOLO版本的成功基础上进行了进一步的创新&#xff0c;引入了全新的特性和改进&#xff0c;以进一步提升性能和灵活性。作为一个高速、精准且易于操作的设计&#xff0c;YO…...

2309ddocx02文档

风格,页眉和页脚等内容与主要分开,允许在起始文档中放大量自定义,然后在生成文档中显示. 打开文档 from docx import Document document Document() document.save("test.docx")真正打开文档 要用文件名打开文档: document Document("existing-document-f…...

第一章初识微服务

文章目录 认识微服务单体架构分布式架构需要考虑的问题 微服务微服务的具体架构微服务技术对比企业中的技术需求 总结 服务拆分注意事项 认识微服务 随着互联网行业的发展&#xff0c;对服务的要求也越来越高&#xff0c;服务架构也从单体架构逐渐演变为现在流行的微服务架构。…...

微信小程序电影票订票小程序软件设计与实现

摘 要 我们的生活水平正在不断的提高&#xff0c;然而提高的一个重要的侧面表现就是更加注重我们的娱乐生活。电影是我们都喜欢的一种娱乐方式&#xff0c;各式各样的电影给我们带来的喜悦也是大不相同的。带来快乐的同时也因为其复杂、繁琐的流程让电影爱好者们变得烦躁起来。…...

Redis 缓存预热+缓存雪崩+缓存击穿+缓存穿透

面试题&#xff1a; 缓存预热、雪萌、穿透、击穿分别是什么&#xff1f;你遇到过那几个情况&#xff1f;缓存预热你是怎么做的&#xff1f;如何造免或者减少缓存雪崩&#xff1f;穿透和击穿有什么区别&#xff1f;他两是一个意思还是载然不同&#xff1f;穿适和击穿你有什么解…...

19c补丁后oracle属主变化,导致不能识别磁盘组

补丁后服务器重启&#xff0c;数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后&#xff0c;存在与用户组权限相关的问题。具体表现为&#xff0c;Oracle 实例的运行用户&#xff08;oracle&#xff09;和集…...

装饰模式(Decorator Pattern)重构java邮件发奖系统实战

前言 现在我们有个如下的需求&#xff0c;设计一个邮件发奖的小系统&#xff0c; 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式&#xff08;Decorator Pattern&#xff09;允许向一个现有的对象添加新的功能&#xff0c;同时又不改变其…...

关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案

问题描述&#xff1a;iview使用table 中type: "index",分页之后 &#xff0c;索引还是从1开始&#xff0c;试过绑定后台返回数据的id, 这种方法可行&#xff0c;就是后台返回数据的每个页面id都不完全是按照从1开始的升序&#xff0c;因此百度了下&#xff0c;找到了…...

[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?

论文网址&#xff1a;pdf 英文是纯手打的&#xff01;论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误&#xff0c;若有发现欢迎评论指正&#xff01;文章偏向于笔记&#xff0c;谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)

UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中&#xff0c;UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化&#xf…...

【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具

第2章 虚拟机性能监控&#xff0c;故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令&#xff1a;jps [options] [hostid] 功能&#xff1a;本地虚拟机进程显示进程ID&#xff08;与ps相同&#xff09;&#xff0c;可同时显示主类&#x…...

Rapidio门铃消息FIFO溢出机制

关于RapidIO门铃消息FIFO的溢出机制及其与中断抖动的关系&#xff0c;以下是深入解析&#xff1a; 门铃FIFO溢出的本质 在RapidIO系统中&#xff0c;门铃消息FIFO是硬件控制器内部的缓冲区&#xff0c;用于临时存储接收到的门铃消息&#xff08;Doorbell Message&#xff09;。…...

#Uniapp篇:chrome调试unapp适配

chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器&#xff1a;Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...

人机融合智能 | “人智交互”跨学科新领域

本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...

【C++特殊工具与技术】优化内存分配(一):C++中的内存分配

目录 一、C 内存的基本概念​ 1.1 内存的物理与逻辑结构​ 1.2 C 程序的内存区域划分​ 二、栈内存分配​ 2.1 栈内存的特点​ 2.2 栈内存分配示例​ 三、堆内存分配​ 3.1 new和delete操作符​ 4.2 内存泄漏与悬空指针问题​ 4.3 new和delete的重载​ 四、智能指针…...