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

【优选算法 — 滑动窗口】最大连续1的个数 将 x 减到0的最小操作数

  

 


   最大连续1的个数  


  最大连续1的个数


   题目描述  

  题目解析  

  1. 给我们一个元素全是0或者1的数组,和一个整数 k ,然后让我们在数组选出最多的 k 个0;
  2. 这里翻转最多 k 个0的意思,是翻转 0 的个数<= k,而不是一定要翻转 k 个0; 
  3. 然后把这 k 个0翻转成1,翻转完成后,找出数组中,连续1的最大个数。

 

  算法原理  


如果按照这个题,直接去把0翻转成1,我们会发现这个操作非常麻烦,因为如果后续还要枚举数组中别的0,就要先把刚刚翻转过的1翻转回0,代码也不好写;

通过上述两个例子,求最大连续1的个数的过程中,我们并没有真正地对0进行翻转,所以我们是可以不用翻转的;

我们只需要在数组中,找一段元素连续为0的区域,并且0的个数不超过k即可;

换而言之,只要这段区域的0的个数不超过k,那么就是一定可以成功翻转的,我们没必要真正地去翻转。

所以上述的问题可以转换成:找出最长子数组,0的个数不超过k个;


   解法一:暴力枚举 + zero计数器  


  • 既然要找最长子数组,我们就固定一个起点,然后不断枚举所有0的个数不超过k的子数组;
  • 并且返回所有子数组中,长度最大的子数组即可。

在暴力枚举的过程中,我们需要定义一个变量,来计数子数组中0的个数;

我们所有的优化方法,都是建立在暴力枚举的基础上,来做优化的,所以要考虑清楚暴力枚举的要点和细节,再在这些细节和要点上总结规律,并作出优化。

如果是暴力枚举的话,此时在 right 到达合适的位置后,left++,right = left,并且重复上面的过程;

但是我们可以发现,在后续的left 向后枚举的过程中,只要 left还在前面3个1的位置,right 能到达的最远位置是不变的;

 我们要对上述枚举的细节做优化。


  解法二:滑动窗口  


 

left 移动到能让 zero=2 的位置,此时只需要让 right 继续向后挪动


  1. left = 0, right =0 ;
  2. 进窗口 (right=1,无视;right = 0,zero++);
  3. 判段(zero > k) (3和4是循环)
  4. 出窗口(left = 1,无视;left = 0,zero--);
  5. 更新结果

  编写代码  

  时间复杂度:

虽然有两层循环,但是根据实际过程,时间复杂度 O(N);

   空间复杂度:

只定义了有限的变量,所以是O(1) 


  将 x 减到0的最小操作数  


将 x 减到0的最小操作数

题目描述


  转换思路:找到数组中,长度最长,且和为 sum - x 的子数组  


如果我们直接按照题目的要求,每次操作都删除数组最左边,或者最右边的元素,使得 x=0,那么这道题的操作是非常麻烦的,因为能删除的方法非常多;

如果正面比较难,我们就使用“正难则反”的方法,这是非常重要的一点;

当我们计算数组两边的区间比较难找,我们可以转换思路,求中间的这一个连续的区间之和

 

  • 我们只需要在数组中间找一段连续的区域,这段区域所有元素之和 target 等于 sum - x 即可;
  • 题目要求的是最小操作数,所以是要找 左边区间 和 右边区间 的元素个数之和最小的情况即可;
  • 进而转换为,在这个数组中,找到一块连续的区域,这个区域的所有元素之和,等于sum-x;
  • 并且这个连续的区域是要最长的,长度设置为 len
  • 找到最长的 len,返回 length - len 即可

   解法:滑动窗口   


随机定义一个数组,来发现规律 

定义 sum1 变量,来标记 right 和 left 中间这段区域的和;


  在 right 向后遍历的时候:  

  1. 当 sum1 > target 时,固定 right,移动 left
  2. 当 sum1 = target 时,先更新 len,再移动 right,
  3. 如果出现 sum1 >= target 的情况,按照上面的步骤处理

  证明 right 不需要往后移动:

此时 right 会停下,是因为刚刚好改变 sum1 和 target 的关系,再更新 len 之后,left++;

此时 left 在更新之后,left 和 right 中间的区域之和一定是小于 target 的,所以 right 不需要 --;

  1. left = 0, right =0 ;
  2. 进窗口(sum1 += num[right++]);
  3. 判断sum1 > target(注意:sum = target 是我们要的结果,而判断是用来调整结果的,所以不写=)
  4. 出窗口(sum1 -=nums[left++]),3 和 4 是循环
  5. 更新结果 (判断 sum1 是等于还是小于 target,==才更新结果);

 编写代码 

上述情况是因为,在刚刚好遍历完成所有数组元素,sum1 才刚好等于 target 的,此时 len虽然还是0,但是只要最终结果返回 n - len ,依旧是正确答案;

但是也有在遍历完所有数组元素,sum1 都不能等于 target 的,所以要在返回结果时判断;

而上述示例二在执行到 return 时,刚好 len 也是0,但是要返回 -1;两种情况就刚好重合了


  修改代码   

  ​​

​​

相关文章:

【优选算法 — 滑动窗口】最大连续1的个数 将 x 减到0的最小操作数

最大连续1的个数 最大连续1的个数 题目描述 题目解析 给我们一个元素全是0或者1的数组&#xff0c;和一个整数 k &#xff0c;然后让我们在数组选出最多的 k 个0&#xff1b;这里翻转最多 k 个0的意思&#xff0c;是翻转 0 的个数< k&#xff0c;而不是一定要翻转 k …...

《TCP/IP网络编程》学习笔记 | Chapter 8:域名及网络地址

《TCP/IP网络编程》学习笔记 | Chapter 8&#xff1a;域名及网络地址 《TCP/IP网络编程》学习笔记 | Chapter 8&#xff1a;域名及网络地址域名系统什么是域名&#xff1f;DNS 服务器IP 地址和域名之间的转换使用域名的必要性利用域名获取 IP 地址利用 IP 地址获取域名 基于 Wi…...

FastHTML快速入门:调试模式和 URL中的变量

调试模式 FastHTML基于FastAPI友好的装饰器模式来指定URL&#xff0c;并添加了额外功能&#xff1a; main.py from fasthtml.common import * app, rt fast_app() rt("/") def get():return Titled("FastHTML", P("让我们开始吧&#xff01;"…...

C++高级编程(8)

八、标准IO库 1.输入输出流类 1)非格式化输入输出 2)put #include <iostream> #include <string> ​ using namespace std; int main() {string str "123456789";for (int i str.length() - 1; i > 0; i--) {cout.put(str[i]); //从最后一个字符开…...

AUTOSAR_EXP_ARAComAPI的7章笔记(2)

☞返回总目录 相关总结&#xff1a;服务发现实现策略总结 7.2 服务发现的实现策略 如前面章节所述&#xff0c;ara::com 期望产品供应商实现服务发现的功能。服务发现功能基本上是在 API 级别通过 FindService、OfferService 和 StopOfferService 方法定义的&#xff0c;协议…...

【C++】 C++游戏设计---五子棋小游戏

1. 游戏介绍 一个简单的 C 五子棋小游戏 1.1 游戏规则&#xff1a; 双人轮流输入下入点坐标横竖撇捺先成五子连线者胜同一坐标点不允许重复输入 1.2 初始化与游戏界面 初始化界面 X 输入坐标后 O 输入坐标后 X 先达到胜出条件 2. 源代码 #include <iostream> #i…...

仿RabitMQ 模拟实现消息队列项目开发文档2(个人项目)

项目需求分析 核心概念 现在需要将这个项目梳理清楚了&#xff0c;便于之后的代码实现。项目中具有一个生产消费模型&#xff1a; 其中生产者和消费者的个数是可以灵活改变的&#xff0c;让系统资源更加合理的分配。消息队列的主逻辑和上面的逻辑基本一样&#xff0c;只不过我…...

李佳琦回到巅峰背后,双11成直播电商分水岭

时间倏忽而过&#xff0c;又一年的双11即将宣告结束。 从双11正式开始前的《新所有女生的offer》&#xff0c;到被作为“比价”标杆被其他平台直播间蹭、被与其他渠道品牌比较&#xff0c;再到直播间运营一时手快多发了红包……整个双11周期下来&#xff0c;李佳琦直播间在刷新…...

云计算在教育领域的应用

&#x1f493; 博客主页&#xff1a;瑕疵的CSDN主页 &#x1f4dd; Gitee主页&#xff1a;瑕疵的gitee主页 ⏩ 文章专栏&#xff1a;《热点资讯》 云计算在教育领域的应用 云计算在教育领域的应用 云计算在教育领域的应用 引言 云计算概述 定义与原理 发展历程 云计算的关键技…...

C语言 | Leetcode C语言题解之第543题二叉树的直径

题目&#xff1a; 题解&#xff1a; typedef struct TreeNode Node;int method (Node* root, int* max) {if (root NULL) return 0;int left method (root->left, max);int right method (root->right, max);*max *max > (left right) ? *max : (left right);…...

6、If、While、For、Switch

6、If、While、For、Switch 一、If 1、if-else if (boolean) {代码块 } else if (boolean) {代码块 } else if (boolean) {代码块 } else { // 默认情况代码块 }关于IDEA单元测试控制台不能输入数据的问题&#xff1a; https://blog.csdn.net/m0_72900498/article/details/…...

萤石设备视频接入平台EasyCVR多品牌摄像机视频平台海康ehome平台(ISUP)接入EasyCVR不在线如何排查?

随着智慧城市和数字化转型的推进&#xff0c;视频监控系统已成为保障公共安全、提升管理效率的重要工具。特别是在大中型项目中&#xff0c;跨区域的网络化视频监控需求日益增长&#xff0c;这要求视频监控管理平台不仅要具备强大的视频资源管理能力&#xff0c;还要能够适应多…...

【多线程】线程池如何知道一个线程的任务已经完成

目录 1. 说明2. 任务的生命周期3. 状态更新4. 线程间的协作5. 内部数据结构6. 回调与通知7. 线程池的关闭与清理 1. 说明 1.线程池通过一系列内部机制来知道一个线程的任务已经完成。2.这些机制主要涉及任务的生命周期管理、状态更新以及线程间的协作。 2. 任务的生命周期 1…...

Transformer介绍(一)

Transformer是一种特殊的神经网络&#xff0c;一种机器学习模型。 谷歌在2017年推出的原版Transformer&#xff0c;论文《Attention Is All You Need》&#xff0c;专注于将一种语言的文本翻译成另一种。 而我们要关注的Transformer变种&#xff0c;即构建ChatGPT等工具的模型…...

[CKS] TLS Secrets创建与挂载

目前的所有题目为2024年10月后更新的最新题库&#xff0c;考试的k8s版本为1.31.1 BackGround 您必须使用存储在TLS Secret中的SSL文件&#xff0c;来保护Web 服务器的安全访问。 Task 在clever-cactus namespace中为名为clever-cactus的现有Deployment创建名为clever-cactu…...

java双向链表解析实现双向链表的创建含代码

双向链表 一.双向链表二.创建MyListCode类实现双向链表创建一.AddFirst创建&#xff08;头插法&#xff09;二.AddLast创建&#xff08;尾叉法&#xff09;三.size四.remove(指定任意节点的首位删除)五.removeAll(包含任意属性值的所有删除)六.AddIndex(给任意位置添加一个节点…...

【Kafka-go】golang的kafka应用

网络上关于go的Kafka还是比较少的今天就先出一篇入门级别的&#xff0c;之后再看看能能出一个公司业务场景中的消息流。 一、下载github.com/segmentio/kafka-go包 go get github.com/segmentio/kafka-go二、建立kafka连接 正常来说下面的配置host topic partition 应该写在…...

redis:set集合命令,内部编码,使用场景

个人主页 &#xff1a; 个人主页 个人专栏 &#xff1a; 《数据结构》 《C语言》《C》《Linux》《网络》 《redis学习笔记》 文章目录 前言命令SADDSMEMBERSSISMEMBERSCARDSPOPSMOVESREM集合间操作SINTERSINTERSTORESUNIONSUNIONSTORESDIFFSDIFFSTORE 内部编码使用场景总结 前言…...

45期代码随想录算法营总结

代码随想录训练营总结与收获 在为期60天的代码随想录训练营结束后&#xff0c;我感慨良多。这段时间不仅让我在编程技能上有了明显的提升&#xff0c;更让我在学习习惯和时间管理上有了深刻的反思和改变。 报名参加这个训练营对我来说是一个重要的监督机制。之前我总是拖延&a…...

深入理解Java中的instanceof关键字及接口新特性:方法实现的可能性

目录 引言 1. 什么是instanceof关键字&#xff1f; 1.1 语法结构 1.2 instanceof的用法示例 1.3 instanceof的应用场景 2. Java中的接口能包含方法实现吗&#xff1f; 2.1 默认方法&#xff08;Default Method&#xff09; 2.2 静态方法&#xff08;Static Method&…...

基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销&#xff0c;平衡网络负载&#xff0c;延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...

centos 7 部署awstats 网站访问检测

一、基础环境准备&#xff08;两种安装方式都要做&#xff09; bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats&#xff0…...

NLP学习路线图(二十三):长短期记忆网络(LSTM)

在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...

【分享】推荐一些办公小工具

1、PDF 在线转换 https://smallpdf.com/cn/pdf-tools 推荐理由&#xff1a;大部分的转换软件需要收费&#xff0c;要么功能不齐全&#xff0c;而开会员又用不了几次浪费钱&#xff0c;借用别人的又不安全。 这个网站它不需要登录或下载安装。而且提供的免费功能就能满足日常…...

面向无人机海岸带生态系统监测的语义分割基准数据集

描述&#xff1a;海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而&#xff0c;目前该领域仍面临一个挑战&#xff0c;即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...

安全突围:重塑内生安全体系:齐向东在2025年BCS大会的演讲

文章目录 前言第一部分&#xff1a;体系力量是突围之钥第一重困境是体系思想落地不畅。第二重困境是大小体系融合瓶颈。第三重困境是“小体系”运营梗阻。 第二部分&#xff1a;体系矛盾是突围之障一是数据孤岛的障碍。二是投入不足的障碍。三是新旧兼容难的障碍。 第三部分&am…...

SQL慢可能是触发了ring buffer

简介 最近在进行 postgresql 性能排查的时候,发现 PG 在某一个时间并行执行的 SQL 变得特别慢。最后通过监控监观察到并行发起得时间 buffers_alloc 就急速上升,且低水位伴随在整个慢 SQL,一直是 buferIO 的等待事件,此时也没有其他会话的争抢。SQL 虽然不是高效 SQL ,但…...

mac 安装homebrew (nvm 及git)

mac 安装nvm 及git 万恶之源 mac 安装这些东西离不开Xcode。及homebrew 一、先说安装git步骤 通用&#xff1a; 方法一&#xff1a;使用 Homebrew 安装 Git&#xff08;推荐&#xff09; 步骤如下&#xff1a;打开终端&#xff08;Terminal.app&#xff09; 1.安装 Homebrew…...

Bean 作用域有哪些?如何答出技术深度?

导语&#xff1a; Spring 面试绕不开 Bean 的作用域问题&#xff0c;这是面试官考察候选人对 Spring 框架理解深度的常见方式。本文将围绕“Spring 中的 Bean 作用域”展开&#xff0c;结合典型面试题及实战场景&#xff0c;帮你厘清重点&#xff0c;打破模板式回答&#xff0c…...

【Elasticsearch】Elasticsearch 在大数据生态圈的地位 实践经验

Elasticsearch 在大数据生态圈的地位 & 实践经验 1.Elasticsearch 的优势1.1 Elasticsearch 解决的核心问题1.1.1 传统方案的短板1.1.2 Elasticsearch 的解决方案 1.2 与大数据组件的对比优势1.3 关键优势技术支撑1.4 Elasticsearch 的竞品1.4.1 全文搜索领域1.4.2 日志分析…...