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

【算法】滑动窗口——将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的最小操作数”这道题的思路历程&#xff0c;从最开始的想法到代码提交的详细记录&#xff0c;有需要借鉴即可。 目录 1.题目2.代码示例3.细节3.1left越界3.2特殊情况 4.总结 1.题目 题目链接&#xff1a;LINK 看题目意思是就是给你一个数X&…...

《引爆流量获客技术》实操方法,手把手教你搭建盈利流量池

[1]-先导课.mp4 [2]-第1节&#xff1a;设计客户终身价值的方法和买客户思维.mp4 [3]-第2节&#xff1a;【渠道模型】解决谁是我的客户如何找到.mp4 [4]-第3节&#xff1a;【诱饵模型】解决 如何获得更多的客户.mp4 [5]-第4节&#xff1a;【钩子模型】解决让目标客户主动找你…...

【记录】常见的前端设计系统(Design System)

解释一下设计系统的定义&#xff0c;以及在国内&#xff0c;都有那些优秀的设计系统可以学习&#xff0c;希望可以帮到大家。 什么是设计系统&#xff08;Design System)&#xff1f; 设计系统&#xff08;Design System&#xff09;是一套综合性的指导原则、组件和规则&…...

如何使用Whisper音频合成模型

Whisper 是一个通用语音识别模型&#xff0c;由 OpenAI 开发。它可以识别多种语言的语音&#xff0c;并将其转换为文本。Whisper 模型采用了深度学习技术&#xff0c;具有高准确性和鲁棒性。 1、技术原理及架构 Whisper 的工作原理&#xff1a;音频被分割成 30 秒的片段&#…...

网络相关笔记

IPv4地址 IPv4地址通常以“点分十进制”形式书写&#xff0c;即四个0-255之间的十进制数&#xff0c;各数之间用英文句点&#xff08;.&#xff09;分隔&#xff0c;例如&#xff1a;192.0.2.1。总共32位的地址空间可以表示大约42亿个不同的地址。 IPv4地址结构包括&#xff…...

由C# yield return引发的思考

前言 当我们编写 C# 代码时&#xff0c;经常需要处理大量的数据集合。在传统的方式中&#xff0c;我们往往需要先将整个数据集合加载到内存中&#xff0c;然后再进行操作。但是如果数据集合非常大&#xff0c;这种方式就会导致内存占用过高&#xff0c;甚至可能导致程序崩溃。 …...

【问题解决】EasyExcel导出数据,并将数据中的实体类url转为图片

EasyExcel导出数据&#xff0c;并将数据中的实体类url转为图片 在导出excel数据时&#xff0c;用户要求把存储二维码url转为图片保存&#xff0c;然后研究了一下具体实现。 代码展示&#xff1a; public void exportData(String pointName, String districtName, String str…...

winform植物大战僵尸

winform植物大战僵尸 植物大战僵尸源码 半成品 需要的拿去学习 登陆注册选择关卡 向日葵 豌豆射手 双枪豌豆射手 项目获取&#xff1a; 项目获取&#xff1a;typora: typora/img (gitee.com) 备用项目获取链接1&#xff1a;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开源库移植并交叉编译到一个嵌入式平台)&#xff0c;用了好几年了&#xff0c;今天用来挂测一批新的采集视频mp4文件&#x…...

mysql基础概念

文章目录 登录mysqlmysql和mysqld数据库操作主流数据库MYSQL架构SQL分类 登录mysql 登录mysql连接服务器&#xff0c;mysql连接时可以指明主机用-h选项&#xff0c;然后就可以指定主机Ip地址&#xff0c;-P可以指定端口号 -u指定登录用户 -P指定登录密码 查看系统中有无mysql&…...

成功案例(IF=7.3)| 转录组+蛋白质组+代谢组联合分析分析揭示胰腺癌中TAM2相关的糖酵解和丙酮酸代谢重构

研究背景 肿瘤的进展和发展需要癌细胞的代谢重编程&#xff0c;癌细胞能量代谢模式的改变可以满足快速增殖和适应肿瘤微环境的需要。肿瘤微环境&#xff08;TME&#xff09;中的代谢状态受到多种因素的影响&#xff0c;包括血管生成、与其他细胞的相互作用和系统代谢。代谢异质…...

【C++ | 函数】默认参数、哑元参数、函数重载、内联函数

&#x1f601;博客主页&#x1f601;&#xff1a;&#x1f680;https://blog.csdn.net/wkd_007&#x1f680; &#x1f911;博客内容&#x1f911;&#xff1a;&#x1f36d;嵌入式开发、Linux、C语言、C、数据结构、音视频&#x1f36d; ⏰发布时间⏰&#xff1a;2024-05-04 1…...

Spring事件

&#x1f4dd;个人主页&#xff1a;五敷有你 &#x1f525;系列专栏&#xff1a;Spring⛺️稳中求进&#xff0c;晒太阳 Spring事件 简洁 Spring Event&#xff08;Application Event&#xff09;就是一个观察者模式&#xff0c;一个bean处理完任务后希望通知其他Bean的…...

mysql安装及基础设置

关系型数据库 MySQL是一种关系型数据库管理系统&#xff0c;采用了关系模型来组织数据的数据库&#xff0c;关系数据库将数据保存在不同的表中&#xff0c;用户通过查询 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视频流

最近有个小活其中有涉及播放大华及海康摄像头视频流的需求&#xff0c;经调查发现可以使用webrtc来实现相关功能&#xff0c;记录一下&#xff0c;步骤如下&#xff1a; &#xff11;、下载webrtc &#xff1a;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 近期重磅发布&#xff0c;发布了 8B 和 70B 参数量的模型&#xff0c;lmdeploy团队对 Llama 3 部署进行了光速支持&#xff01;&#xff01;&#xff01; 书生浦语和机智流社区同学光速投稿了 LMDeploy 高效量化部署 Llam…...

SK Hynix 探索超低温技术,开启400层以上3D NAND制造新时代

随着存储技术的飞速发展&#xff0c;SK Hynix作为韩国存储巨头&#xff0c;正以前沿的制造技术引领行业变革。据韩国媒体TheElec独家报道&#xff0c;SK Hynix正积极研究在超低温条件下生产3D NAND闪存的可能性&#xff0c;此举有望助力其下一代产品突破400层的技术瓶颈&#x…...

DevOps工具链集成:GitLab CI、Jenkins与Argo CD如何选?

DevOps工具链集成&#xff1a;GitLab CI、Jenkins与Argo CD如何选&#xff1f; 在DevOps实践中&#xff0c;工具链的选型直接影响交付效率与系统稳定性。GitLab CI、Jenkins和Argo CD作为主流工具&#xff0c;分别覆盖持续集成&#xff08;CI&#xff09;、持续交付&#xff0…...

Stable Diffusion 2.0超分实战:4倍放大图片还能保持清晰度的秘密

Stable Diffusion 2.0超分实战&#xff1a;4倍放大图片还能保持清晰度的秘密 在数字图像处理领域&#xff0c;超分辨率技术一直是设计师和开发者关注的焦点。传统放大方法往往导致图像模糊、细节丢失&#xff0c;而基于深度学习的超分方案正在改变这一局面。Stable Diffusion 2…...

边缘智能部署:AI模型在边缘节点的轻量化改造

边缘智能部署&#xff1a;AI模型在边缘节点的轻量化改造&#x1f4da; 本章学习目标&#xff1a;深入理解AI模型在边缘节点的轻量化改造的核心概念与实践方法&#xff0c;掌握关键技术要点&#xff0c;了解实际应用场景与最佳实践。本文属于《云原生、云边端一体化与算力基建&a…...

GLM-4.1V-9B-Base模型微调入门:使用accelerate库进行高效参数优化

GLM-4.1V-9B-Base模型微调入门&#xff1a;使用accelerate库进行高效参数优化 1. 引言 想为特定业务场景定制一个强大的多模态AI模型&#xff1f;GLM-4.1V-9B-Base作为支持图文理解与生成的大模型&#xff0c;通过微调可以快速适配各种下游任务。本文将带你从零开始&#xff…...

新手零压力入门,快马ai带你三步搞定nodejs环境配置

最近在帮几个朋友入门Node.js时&#xff0c;发现很多新手卡在了环境配置这一步。作为一个过来人&#xff0c;我完全理解那种面对命令行手足无措的感觉。好在现在有了InsCode(快马)平台&#xff0c;可以快速生成一个专为Node.js新手设计的入门项目模板&#xff0c;把抽象的配置过…...

别再手动测试了!教你用ThinkPHP6+Workerman/MQTT搭建一个本地MQTT消息调试台

基于ThinkPHP6与Workerman/MQTT构建物联网调试平台的完整指南 物联网开发中&#xff0c;MQTT协议因其轻量级和高效性成为设备通信的首选方案。但调试MQTT消息往往依赖命令行工具或第三方平台&#xff0c;效率低下且缺乏灵活性。本文将展示如何利用ThinkPHP6框架配合Workerman/M…...

别再傻傻分不清了!一文搞懂微信支付代金券和商家券的核心区别与适用场景

微信支付代金券VS商家券&#xff1a;技术选型与场景化应用指南 在数字化营销的浪潮中&#xff0c;优惠券作为连接商户与消费者的重要纽带&#xff0c;其技术实现方式直接影响营销效果与用户体验。微信支付提供的代金券与商家券看似功能相似&#xff0c;实则存在架构级差异。本文…...

字符串拆分合并

贪心算法,最长限制。 import reclass TextFilter:def __init__(self):# 字符映射规则self.char_map = {# 省略号 → 停顿…: ,, ...: ,,: ,,# 破折号 → 停顿——: ,, —: ,,# 书名号 → 直接删除《: , 》: , 〈: , 〉: ,# 其他特殊符号 → 删除*: , /: , #: ,}# 需要保留的…...

Overleaf-Workshop:在VSCode中实现Open Overleaf项目的无缝协作与高效管理

Overleaf-Workshop&#xff1a;在VSCode中实现Open Overleaf项目的无缝协作与高效管理 【免费下载链接】Overleaf-Workshop Open Overleaf/ShareLaTex projects in vscode, with full collaboration support. 项目地址: https://gitcode.com/gh_mirrors/ov/Overleaf-Workshop…...

AI头像生成器实战:用Qwen3-32B为你的社交头像设计专属描述文案

AI头像生成器实战&#xff1a;用Qwen3-32B为你的社交头像设计专属描述文案 1. 为什么你需要一个AI头像生成器 在社交媒体时代&#xff0c;一个独特的头像已经成为个人品牌的重要组成部分。无论是LinkedIn上的专业形象&#xff0c;还是Instagram上的创意展示&#xff0c;头像都…...