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



最大连续1的个数
最大连续1的个数
题目描述

题目解析
- 给我们一个元素全是0或者1的数组,和一个整数 k ,然后让我们在数组选出最多的 k 个0;
- 这里翻转最多 k 个0的意思,是翻转 0 的个数<= k,而不是一定要翻转 k 个0;
- 然后把这 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 继续向后挪动


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

时间复杂度:
虽然有两层循环,但是根据实际过程,时间复杂度 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 向后遍历的时候:
- 当 sum1 > target 时,固定 right,移动 left
- 当 sum1 = target 时,先更新 len,再移动 right,
- 如果出现 sum1 >= target 的情况,按照上面的步骤处理

证明 right 不需要往后移动:

此时 right 会停下,是因为刚刚好改变 sum1 和 target 的关系,再更新 len 之后,left++;
此时 left 在更新之后,left 和 right 中间的区域之和一定是小于 target 的,所以 right 不需要 --;
- left = 0, right =0 ;
- 进窗口(sum1 += num[right++]);
- 判断sum1 > target(注意:sum = target 是我们要的结果,而判断是用来调整结果的,所以不写=)
- 出窗口(sum1 -=nums[left++]),3 和 4 是循环
- 更新结果 (判断 sum1 是等于还是小于 target,==才更新结果);
编写代码

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

但是也有在遍历完所有数组元素,sum1 都不能等于 target 的,所以要在返回结果时判断;
而上述示例二在执行到 return 时,刚好 len 也是0,但是要返回 -1;两种情况就刚好重合了;
修改代码

相关文章:
【优选算法 — 滑动窗口】最大连续1的个数 将 x 减到0的最小操作数
最大连续1的个数 最大连续1的个数 题目描述 题目解析 给我们一个元素全是0或者1的数组,和一个整数 k ,然后让我们在数组选出最多的 k 个0;这里翻转最多 k 个0的意思,是翻转 0 的个数< k,而不是一定要翻转 k …...
《TCP/IP网络编程》学习笔记 | Chapter 8:域名及网络地址
《TCP/IP网络编程》学习笔记 | Chapter 8:域名及网络地址 《TCP/IP网络编程》学习笔记 | Chapter 8:域名及网络地址域名系统什么是域名?DNS 服务器IP 地址和域名之间的转换使用域名的必要性利用域名获取 IP 地址利用 IP 地址获取域名 基于 Wi…...
FastHTML快速入门:调试模式和 URL中的变量
调试模式 FastHTML基于FastAPI友好的装饰器模式来指定URL,并添加了额外功能: main.py from fasthtml.common import * app, rt fast_app() rt("/") def get():return Titled("FastHTML", P("让我们开始吧!"…...
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)
☞返回总目录 相关总结:服务发现实现策略总结 7.2 服务发现的实现策略 如前面章节所述,ara::com 期望产品供应商实现服务发现的功能。服务发现功能基本上是在 API 级别通过 FindService、OfferService 和 StopOfferService 方法定义的,协议…...
【C++】 C++游戏设计---五子棋小游戏
1. 游戏介绍 一个简单的 C 五子棋小游戏 1.1 游戏规则: 双人轮流输入下入点坐标横竖撇捺先成五子连线者胜同一坐标点不允许重复输入 1.2 初始化与游戏界面 初始化界面 X 输入坐标后 O 输入坐标后 X 先达到胜出条件 2. 源代码 #include <iostream> #i…...
仿RabitMQ 模拟实现消息队列项目开发文档2(个人项目)
项目需求分析 核心概念 现在需要将这个项目梳理清楚了,便于之后的代码实现。项目中具有一个生产消费模型: 其中生产者和消费者的个数是可以灵活改变的,让系统资源更加合理的分配。消息队列的主逻辑和上面的逻辑基本一样,只不过我…...
李佳琦回到巅峰背后,双11成直播电商分水岭
时间倏忽而过,又一年的双11即将宣告结束。 从双11正式开始前的《新所有女生的offer》,到被作为“比价”标杆被其他平台直播间蹭、被与其他渠道品牌比较,再到直播间运营一时手快多发了红包……整个双11周期下来,李佳琦直播间在刷新…...
云计算在教育领域的应用
💓 博客主页:瑕疵的CSDN主页 📝 Gitee主页:瑕疵的gitee主页 ⏩ 文章专栏:《热点资讯》 云计算在教育领域的应用 云计算在教育领域的应用 云计算在教育领域的应用 引言 云计算概述 定义与原理 发展历程 云计算的关键技…...
C语言 | Leetcode C语言题解之第543题二叉树的直径
题目: 题解: 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单元测试控制台不能输入数据的问题: https://blog.csdn.net/m0_72900498/article/details/…...
萤石设备视频接入平台EasyCVR多品牌摄像机视频平台海康ehome平台(ISUP)接入EasyCVR不在线如何排查?
随着智慧城市和数字化转型的推进,视频监控系统已成为保障公共安全、提升管理效率的重要工具。特别是在大中型项目中,跨区域的网络化视频监控需求日益增长,这要求视频监控管理平台不仅要具备强大的视频资源管理能力,还要能够适应多…...
【多线程】线程池如何知道一个线程的任务已经完成
目录 1. 说明2. 任务的生命周期3. 状态更新4. 线程间的协作5. 内部数据结构6. 回调与通知7. 线程池的关闭与清理 1. 说明 1.线程池通过一系列内部机制来知道一个线程的任务已经完成。2.这些机制主要涉及任务的生命周期管理、状态更新以及线程间的协作。 2. 任务的生命周期 1…...
Transformer介绍(一)
Transformer是一种特殊的神经网络,一种机器学习模型。 谷歌在2017年推出的原版Transformer,论文《Attention Is All You Need》,专注于将一种语言的文本翻译成另一种。 而我们要关注的Transformer变种,即构建ChatGPT等工具的模型…...
[CKS] TLS Secrets创建与挂载
目前的所有题目为2024年10月后更新的最新题库,考试的k8s版本为1.31.1 BackGround 您必须使用存储在TLS Secret中的SSL文件,来保护Web 服务器的安全访问。 Task 在clever-cactus namespace中为名为clever-cactus的现有Deployment创建名为clever-cactu…...
java双向链表解析实现双向链表的创建含代码
双向链表 一.双向链表二.创建MyListCode类实现双向链表创建一.AddFirst创建(头插法)二.AddLast创建(尾叉法)三.size四.remove(指定任意节点的首位删除)五.removeAll(包含任意属性值的所有删除)六.AddIndex(给任意位置添加一个节点…...
【Kafka-go】golang的kafka应用
网络上关于go的Kafka还是比较少的今天就先出一篇入门级别的,之后再看看能能出一个公司业务场景中的消息流。 一、下载github.com/segmentio/kafka-go包 go get github.com/segmentio/kafka-go二、建立kafka连接 正常来说下面的配置host topic partition 应该写在…...
redis:set集合命令,内部编码,使用场景
个人主页 : 个人主页 个人专栏 : 《数据结构》 《C语言》《C》《Linux》《网络》 《redis学习笔记》 文章目录 前言命令SADDSMEMBERSSISMEMBERSCARDSPOPSMOVESREM集合间操作SINTERSINTERSTORESUNIONSUNIONSTORESDIFFSDIFFSTORE 内部编码使用场景总结 前言…...
45期代码随想录算法营总结
代码随想录训练营总结与收获 在为期60天的代码随想录训练营结束后,我感慨良多。这段时间不仅让我在编程技能上有了明显的提升,更让我在学习习惯和时间管理上有了深刻的反思和改变。 报名参加这个训练营对我来说是一个重要的监督机制。之前我总是拖延&a…...
深入理解Java中的instanceof关键字及接口新特性:方法实现的可能性
目录 引言 1. 什么是instanceof关键字? 1.1 语法结构 1.2 instanceof的用法示例 1.3 instanceof的应用场景 2. Java中的接口能包含方法实现吗? 2.1 默认方法(Default Method) 2.2 静态方法(Static Method&…...
网络编程(Modbus进阶)
思维导图 Modbus RTU(先学一点理论) 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议,由 Modicon 公司(现施耐德电气)于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...
conda相比python好处
Conda 作为 Python 的环境和包管理工具,相比原生 Python 生态(如 pip 虚拟环境)有许多独特优势,尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处: 一、一站式环境管理:…...
K8S认证|CKS题库+答案| 11. AppArmor
目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作: 1)、切换集群 2)、切换节点 3)、切换到 apparmor 的目录 4)、执行 apparmor 策略模块 5)、修改 pod 文件 6)、…...
HTML 列表、表格、表单
1 列表标签 作用:布局内容排列整齐的区域 列表分类:无序列表、有序列表、定义列表。 例如: 1.1 无序列表 标签:ul 嵌套 li,ul是无序列表,li是列表条目。 注意事项: ul 标签里面只能包裹 li…...
[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?
论文网址:pdf 英文是纯手打的!论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误,若有发现欢迎评论指正!文章偏向于笔记,谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...
linux 错误码总结
1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...
跨链模式:多链互操作架构与性能扩展方案
跨链模式:多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈:模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展(H2Cross架构): 适配层…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)
宇树机器人多姿态起立控制强化学习框架论文解析 论文解读:交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一) 论文解读:交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...
Element Plus 表单(el-form)中关于正整数输入的校验规则
目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入(联动)2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...
docker 部署发现spring.profiles.active 问题
报错: org.springframework.boot.context.config.InvalidConfigDataPropertyException: Property spring.profiles.active imported from location class path resource [application-test.yml] is invalid in a profile specific resource [origin: class path re…...
