【算法】滑动窗口——将x减到0的最小操作数
本节博客主要是讲的我解“将x减到0的最小操作数”这道题的思路历程,从最开始的想法到代码提交的详细记录,有需要借鉴即可。
目录
- 1.题目
- 2.代码示例
- 3.细节
- 3.1left越界
- 3.2特殊情况
- 4.总结
1.题目
题目链接:LINK

看题目意思是就是给你一个数X,让你拿着数组中的最左边或者最右边的数字与这个数字抵消(相减),直到X为0,或者找不到,如果可以抵消掉,记录拿这个数组中最少的一个数字个数,而且用数组中的值的时候,必须用两头的。
这个暴力求解…都不知道下一次是用左边的数字还是右边的数字,…,基本暴力解法就想不到了。
这里我们老师讲的,说要用到转换思想——“正难则反”
什么意思呢?
其实对于这个题目来说,整个数组可以分为三块,即下图:

说白了就让我们找left + right这两块中最小的数字个数
那可以等效于让我们找 该数组总数字个数 - mind最大数字个数
顺着前面“滑动窗口”的代码思路:
大体就可以写出下面代码:
2.代码示例
class Solution {
public:int minOperations(vector<int>& nums, int x) {int ALsum = 0;int n = nums.size();for(size_t i = 0;i<n;i++){ALsum+=nums[i];}long long target = ALsum - x;//中间的目标值,满足目标值就进行更新结果int ret = -1;//代表两边的长度,取最小值int len = 0;//代表left和right之间的长度,取最大值long long sum = 0;//代表中间区间的和//处理特殊情况if (sum == target){return n;}for(int right = 0,left = 0; right < n; right++){//进窗口sum+=nums[right];//出窗口while(sum > target && left < right){sum-=nums[left];left++;}//更新结果if(sum == target){len = max(len,right - left + 1);}}return ret = len == 0 ? -1 : n - len;}
};
这个题做完之后感觉还是有一两个坑的,下面进行展示:
3.细节
3.1left越界
这个问题呢,也可以说是X > 整个数组之和,即target小于0,导致了left会不断右移的情况:

class Solution {
public:int minOperations(vector<int>& nums, int x) {int ALsum = 0;int n = nums.size();for(size_t i = 0;i<n;i++){ALsum+=nums[i];}int target = ALsum - x;//中间的目标值,满足目标值就进行更新结果int ret = -1;//代表两边的长度,取最小值int len = 0;//代表left和right之间的长度,取最大值int sum = 0;//代表中间区间的和for(int right = 0,left = 0; right < n; right++){//进窗口sum+=nums[right];//出窗口while(sum > target){sum-=nums[left];left++;}//更新结果if(sum == target){len = max(len,right - left + 1);}}return ret = len == 0 ? -1 : n - len;}
};
这个主要是越界问题,是left越界了。
3.2特殊情况

class Solution {
public:int minOperations(vector<int>& nums, int x) {int ALsum = 0;int n = nums.size();for(size_t i = 0;i<n;i++){ALsum+=nums[i];}int target = ALsum - x;//中间的目标值,满足目标值就进行更新结果int ret = -1;//代表两边的长度,取最小值int len = 0;//代表left和right之间的长度,取最大值int sum = 0;//代表中间区间的和for(int right = 0,left = 0; right < n; right++){//进窗口sum+=nums[right];//出窗口while(sum > target && left < right){sum-=nums[left];left++;}//更新结果if(sum == target){len = max(len,right - left + 1);}}return ret = len == 0 ? -1 : n - len;}
};
这个是出了什么问题呢?就是这是一种数组里的数字全部都与X相消才行,特殊情况吧算是,需要特别处理一下。
我写的这个代码刚好默认是mid组至少有一个数字的,用我写的代码肯定是找不到的,所以需要特殊判断一下。
4.总结
感觉这个题关键是刚上来的转换思想很关键(怪不得是中等题目),其次是想到滑动窗口,这俩细节问题的话可以通过调试调出来。
EOF
相关文章:
【算法】滑动窗口——将x减到0的最小操作数
本节博客主要是讲的我解“将x减到0的最小操作数”这道题的思路历程,从最开始的想法到代码提交的详细记录,有需要借鉴即可。 目录 1.题目2.代码示例3.细节3.1left越界3.2特殊情况 4.总结 1.题目 题目链接:LINK 看题目意思是就是给你一个数X&…...
《引爆流量获客技术》实操方法,手把手教你搭建盈利流量池
[1]-先导课.mp4 [2]-第1节:设计客户终身价值的方法和买客户思维.mp4 [3]-第2节:【渠道模型】解决谁是我的客户如何找到.mp4 [4]-第3节:【诱饵模型】解决 如何获得更多的客户.mp4 [5]-第4节:【钩子模型】解决让目标客户主动找你…...
【记录】常见的前端设计系统(Design System)
解释一下设计系统的定义,以及在国内,都有那些优秀的设计系统可以学习,希望可以帮到大家。 什么是设计系统(Design System)? 设计系统(Design System)是一套综合性的指导原则、组件和规则&…...
如何使用Whisper音频合成模型
Whisper 是一个通用语音识别模型,由 OpenAI 开发。它可以识别多种语言的语音,并将其转换为文本。Whisper 模型采用了深度学习技术,具有高准确性和鲁棒性。 1、技术原理及架构 Whisper 的工作原理:音频被分割成 30 秒的片段&#…...
网络相关笔记
IPv4地址 IPv4地址通常以“点分十进制”形式书写,即四个0-255之间的十进制数,各数之间用英文句点(.)分隔,例如:192.0.2.1。总共32位的地址空间可以表示大约42亿个不同的地址。 IPv4地址结构包括ÿ…...
由C# yield return引发的思考
前言 当我们编写 C# 代码时,经常需要处理大量的数据集合。在传统的方式中,我们往往需要先将整个数据集合加载到内存中,然后再进行操作。但是如果数据集合非常大,这种方式就会导致内存占用过高,甚至可能导致程序崩溃。 …...
【问题解决】EasyExcel导出数据,并将数据中的实体类url转为图片
EasyExcel导出数据,并将数据中的实体类url转为图片 在导出excel数据时,用户要求把存储二维码url转为图片保存,然后研究了一下具体实现。 代码展示: public void exportData(String pointName, String districtName, String str…...
winform植物大战僵尸
winform植物大战僵尸 植物大战僵尸源码 半成品 需要的拿去学习 登陆注册选择关卡 向日葵 豌豆射手 双枪豌豆射手 项目获取: 项目获取:typora: typora/img (gitee.com) 备用项目获取链接1:yifeiyixiang/kamo: 源码下载 (github.com) 备用…...
Pointnet++改进即插即用系列:全网首发UIB轻量化模块
简介:1.该教程提供大量的首发改进的方式,降低上手难度,多种结构改进,助力寻找创新点!2.本篇文章对Pointnet++特征提取模块进行改进,加入UIB,提升性能。3.专栏持续更新,紧随最新的研究内容。 目录 1.理论介绍 2.修改步骤 2.1 步骤一 2.2 步骤二 2.3 步骤三...
【视频格式转换】【ffmepg】对mp4文件进行重新编码输出新的mp4文件
【视频格式转换】【ffmepg】对mp4文件进行重新编码输出新的mp4文件 背景 之前开发调试了个能正常调用ffmpeg解码mp4文件得到yuv数据的testbed(把ffmpeg开源库移植并交叉编译到一个嵌入式平台),用了好几年了,今天用来挂测一批新的采集视频mp4文件&#x…...
mysql基础概念
文章目录 登录mysqlmysql和mysqld数据库操作主流数据库MYSQL架构SQL分类 登录mysql 登录mysql连接服务器,mysql连接时可以指明主机用-h选项,然后就可以指定主机Ip地址,-P可以指定端口号 -u指定登录用户 -P指定登录密码 查看系统中有无mysql&…...
成功案例(IF=7.3)| 转录组+蛋白质组+代谢组联合分析分析揭示胰腺癌中TAM2相关的糖酵解和丙酮酸代谢重构
研究背景 肿瘤的进展和发展需要癌细胞的代谢重编程,癌细胞能量代谢模式的改变可以满足快速增殖和适应肿瘤微环境的需要。肿瘤微环境(TME)中的代谢状态受到多种因素的影响,包括血管生成、与其他细胞的相互作用和系统代谢。代谢异质…...
【C++ | 函数】默认参数、哑元参数、函数重载、内联函数
😁博客主页😁:🚀https://blog.csdn.net/wkd_007🚀 🤑博客内容🤑:🍭嵌入式开发、Linux、C语言、C、数据结构、音视频🍭 ⏰发布时间⏰:2024-05-04 1…...
Spring事件
📝个人主页:五敷有你 🔥系列专栏:Spring⛺️稳中求进,晒太阳 Spring事件 简洁 Spring Event(Application Event)就是一个观察者模式,一个bean处理完任务后希望通知其他Bean的…...
mysql安装及基础设置
关系型数据库 MySQL是一种关系型数据库管理系统,采用了关系模型来组织数据的数据库,关系数据库将数据保存在不同的表中,用户通过查询 sql 来检索数据库中的数据。 yum 方式安装 mysql # yum -y install mysql-server # systemctl start my…...
【prometheus】Pushgateway安装和使用
目录 一、Pushgateway概述 1.1 Pushgateway简介 1.2 Pushgateway优点 1.3 pushgateway缺点 二、测试环境 三、安装测试 3.1 pushgateway安装 3.2 prometheus添加pushgateway 3.3 推送指定的数据格式到pushgateway 1.添加单条数据 2.添加复杂数据 3.SDk-prometheus-…...
【无标题】vue webrtc 播放rtsp视频流
最近有个小活其中有涉及播放大华及海康摄像头视频流的需求,经调查发现可以使用webrtc来实现相关功能,记录一下,步骤如下: 1、下载webrtc :Releases mpromonet/webrtc-streamer GitHub winows下下载&…...
redis进阶--IDEA环境
目录 一、解决redis服务器端口问题 二、java环境下使用redis 三、javaSpringt环境下使用redis 四、redis持久化 1、持久化概念 2、redis持久化策略 3、RDB策略 4、AOF策略 5、混合持久化策略 五、redis事务 1、数据库事务 2、redis事务特点 3、redis事务的作用 4…...
Llama3-Tutorial之LMDeploy高效部署Llama3实践
Llama3-Tutorial之LMDeploy高效部署Llama3实践 Llama 3 近期重磅发布,发布了 8B 和 70B 参数量的模型,lmdeploy团队对 Llama 3 部署进行了光速支持!!! 书生浦语和机智流社区同学光速投稿了 LMDeploy 高效量化部署 Llam…...
SK Hynix 探索超低温技术,开启400层以上3D NAND制造新时代
随着存储技术的飞速发展,SK Hynix作为韩国存储巨头,正以前沿的制造技术引领行业变革。据韩国媒体TheElec独家报道,SK Hynix正积极研究在超低温条件下生产3D NAND闪存的可能性,此举有望助力其下一代产品突破400层的技术瓶颈&#x…...
别再死记公式了!用Multisim仿真软件,10分钟搞懂555定时器的三种工作模式
用Multisim玩转555定时器:可视化学习三种工作模式的终极指南 记得第一次接触555定时器时,我被那些复杂的公式和抽象的工作原理搞得晕头转向。直到一位资深工程师告诉我:"别急着背公式,先看看它怎么工作。"这句话彻底改变…...
灵毓秀-牧神-造相Z-Turbo使用全攻略:从环境检查到作品输出
灵毓秀-牧神-造相Z-Turbo使用全攻略:从环境检查到作品输出 1. 镜像简介与核心功能 灵毓秀-牧神-造相Z-Turbo是一款基于Xinference部署的AI文生图模型服务,专门用于生成《牧神记》中灵毓秀角色的高质量图像。该镜像集成了Gradio交互界面,让用…...
背包模型(求组合)?爬楼梯模型(求排列)?
普通背包模型和爬楼梯模型是非常相似的两个模型。 首先,我们定义一个**“抽象背包模型”**(注意这个抽象背包模型不是前面提到的普通背包模型):给定 n 个物品,装满容积为 m 的背包,求方案数/具体方案/等等…...
MSPM0G3507开发实战:从零搭建Keil工程与SysConfig配置详解
1. 开发环境准备与SDK文件结构解析 第一次接触MSPM0G3507开发板时,我花了整整两天时间才搞明白SDK文件该怎么用。这里分享我的踩坑经验,帮你省下这些时间。首先确认你的开发环境已经安装以下组件: Keil MDK:建议使用5.33版本&…...
JS脚本实现IE11自动跳转Chrome的完整配置指南(含ActiveX控件启用详解)
1. 为什么需要IE11自动跳转Chrome? 很多企业还在使用老旧系统,这些系统往往只兼容IE11浏览器。但IE11性能差、安全性低,用起来特别卡顿。我去年给一家制造企业做系统升级时就遇到过这种情况——他们的ERP系统只能在IE11运行,但财…...
货车行车记录仪被破坏手工修复成功
由于视频记录了打架过程,很重要, 客户在第一次查看时没问题,再次想拷贝,发现内容都没有了只有USC文件,使用容量也有,如图 好在客户没有再次破坏,TS视频文件,同行通过恢复软件恢复&am…...
创维E900V22D_S905L3S(B)芯片-安卓9.0-免拆线刷固件包及短接神器使用指南
1. 创维E900V22D刷机前的准备工作 拿到创维E900V22D机顶盒的第一件事,就是确认它的硬件配置。这个型号采用的是晶晨S905L3S(B)芯片方案,运行的是安卓9.0系统。我遇到过不少朋友因为没看清芯片型号就开刷,结果把盒子刷成砖的案例。所以一定要先…...
5分钟搞定OpenCV摄像头实时监控(附Jupyter避坑指南)
5分钟搞定OpenCV摄像头实时监控(附Jupyter避坑指南) 在计算机视觉领域,实时摄像头监控是最基础也最实用的功能之一。无论是安防监控、人脸识别还是简单的视频采集,OpenCV都提供了简洁高效的接口。但对于Python初学者和Jupyter Not…...
Allegro 17.4约束管理器实战:从基础规则到高速PCB设计优化
1. Allegro约束管理器入门指南 刚接触Allegro 17.4的工程师经常会问:为什么我的PCB设计总是出现DRC报错?为什么高速信号总是不稳定?其实问题的关键往往在于约束管理器的使用。作为Cadence Allegro的核心功能模块,约束管理器就像PC…...
AQM0802字符LCD轻量驱动库:裸机printf级显示方案
1. 项目概述AQM0802 是一款由旭化成(AKM)推出的超低功耗、单色字符型液晶显示模块,采用 COG(Chip-on-Glass)封装工艺,内置 KS0066 兼容控制器。其典型型号为 AQM0802A-YBW,具备 8 字符 2 行的显…...
