【优选算法 — 滑动窗口】最大连续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;两种情况就刚好重合了


  修改代码   

  ​​

​​

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/10699.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

HTML基础

1.HTML基本结构标签 在Visual Studio Code中&#xff0c;使用&#xff01;回车就可以创建一个HTML的基本结构 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"wi…

CSM快速匹配与多分辨率匹配代码实现

0. 简介 CSM在Cartographer中是比较基础且非常适合拓展的功能。他主要的步骤如下图。 主要实现的步骤为&#xff1a; 1&#xff09;获取先验位姿&#xff0c;通过TF获取里程计的值&#xff0c;作为当前scan的预测位姿&#xff0c;将这个预测位姿当做扫描匹配的先验。 2&…

力扣力扣力:动态规划入门(1)

相信大家在第一次学动态规划的时候都是一脸懵逼的&#xff0c;在看了很多题解之后&#xff0c;陷入到了空的“最优子结构”等的大词上&#xff0c;依旧看不懂动态规划到底在干什么。今天我们也是老样子再一次的从零开始学习与讲解&#xff0c;俺也是从零开始学动态规划&#xf…

私域流量时代下的新型商业模式:以开源链动 2 + 1 模式、AI 智能名片、S2B2C 商城小程序源码为例

摘要&#xff1a;本文探讨了私域流量时代的特点及其对商业盈利模式的影响。通过分析从大众消费时代到私域流量时代的转型&#xff0c;阐述了商品到“人”的变化过程。同时&#xff0c;深入研究了开源链动 2 1 模式、AI 智能名片和 S2B2C 商城小程序源码在私域流量发展中的作用…

多模态交互智能体全面解析:定义、架构、学习机制、系统实现、分类、应用场景及评估方法

多模态AI系统很可能会成为我们日常生活中无处不在的存在。使这些系统更具交互性的一种有希望的方法是将它们作为物理和虚拟环境中的智能体。目前&#xff0c;系统利用现有的基础模型作为创建具身智能体的基本构建块。将智能体嵌入这些环境中&#xff0c;有助于模型处理和解释视…

助眠白噪音视频素材哪里找?这些平台帮你快速找到放松素材

在现代社会&#xff0c;信息的轰炸让人们的生活节奏变得越来越快&#xff0c;很多人晚上都在床上辗转反侧&#xff0c;难以入眠。如果你也遇到这样的困扰&#xff0c;想要寻找助眠的白噪音视频素材&#xff0c;那么今天介绍的这些网站将会是你的福音&#xff01;它们提供高质量…

一年四起供应链投毒事件的幕后黑手

前言 2017年&#xff0c;黑客入侵Avast服务器&#xff0c;在CCleaner更新中植入恶意代码&#xff0c;被数百万用户下载。 2017年&#xff0c;M.E.Doc遭黑客攻击&#xff0c;篡改更新植入NotPetya&#xff0c;影响全球公司。 2020年&#xff0c;黑客入侵SolarWinds服务器&…

Qt信号和槽-->day04

Qt信号和槽 标准的信号和槽函数Qt中的槽函数Qt中的信号 connect案例 自定义信号和槽案例分析 信号槽的拓展信号连接信号案例 信号槽的两种连接方式Qt5中的处理方式Qt4中的处理方式Qt5处理信号槽重载问题案例 lambda表达式简单案例Qt中的应用 补充知识点 标准的信号和槽函数 QW…

【超级详细】基于Zynq FPGA对雷龙SD NAND的测试

目录 一、SD NAND特征1.1 SD卡简介1.2 SD卡Block图 二、SD卡样片三、Zynq测试平台搭建3.1 测试流程3.2 SOC搭建 一、SD NAND特征 1.1 SD卡简介 雷龙的SD NAND有很多型号&#xff0c;在测试中使用的是CSNP4GCR01-AMW与CSNP32GCR01-AOW。芯片是基于NAND FLASH和 SD控制器实现的…

linux物理内存管理:node,zone,page

一、总览 对于物理内存内存&#xff0c;linux对内存的组织逻辑从上到下依次是&#xff1a;node&#xff0c;zone&#xff0c;page&#xff0c;这些page是根据buddy分配算法组织的&#xff0c;看下面两张图&#xff1a; 上面的概念做下简单的介绍&#xff1a; Node&#xff1a…

STM32-Flash闪存

目录 一、简介 1、闪存模块组织 2、FLASh基本结构 3、FLash写入和读取操作 4、编程流程 5、选项字节格式 6、选项字节编程步骤 二、读写芯片内部FLASH编程 三、器件电子签名 1、简介 2、编程实现 一、简介 STM32F1系列的FLASH包含程序存储器、系统存储器和选项字节…

数据结构之带头双向循环链表

前言&#xff1a;前面我们实现了顺序表和单链表&#xff0c;这次来实现一个结构更复杂的链表-----带头双向循环链表。不要被它的名字吓到哦&#xff0c;只是结构复杂而已&#xff0c;它的结构更有利于代码的实现。 1 双向循环链表的介绍 有了单链表的基础&#xff0c;要实现这…

10个最常用的Python包,程序员必备!

世界上有超过200,000个Python程序包&#xff08;这只是基于官方的Python程序包索引PyPI托管的程序包&#xff09;。 这就引出了一个问题&#xff1a;拥有这么多的软件包&#xff0c;每个Python程序员都需要学习哪些软件包是最重要的&#xff1f; 为了帮助回答这个问题&#x…

线上问题的排查-java死锁问题如何排查

这里写目录标题 1.java死锁如何排查2.具体步骤1.1识别死锁现象1.2收集线程转储1.3分析线程转储1.4代码审查1.5重现问题1.6使用调试工具1.7.优化和验证 3. 解决方案总结 1.java死锁如何排查 在Java应用程序中&#xff0c;死锁是一个经典的并发问题&#xff0c;它会导致线程永久阻…

shodan(4-5)

以下笔记学习来自B站泷羽Sec&#xff1a; B站泷羽Sec 1. 查看自己的出口IP 可以知晓自己是哪个IP连接的公网 shodan myip2. 指定标题搜索 http.title:内容搜索被挂黑页的网页&#xff1a;获得标题中含有hacked by的IP shodan search --limit 10 --fields ip_str,port htt…

三种风格截然不同的实验室工控界面

三种风格截然不同的实验室工控界面各具特色。一种可能是简洁现代风&#xff0c;以简洁的线条、纯净的色彩和直观的图标&#xff0c;呈现出高效与专业。 另一种或许是科技未来风&#xff0c;运用炫酷的光影效果和立体感十足的设计&#xff0c;展现实验室的前沿科技感。 还有一…

Redis如何保证数据不丢失(可靠性)

本文主要以学习为主&#xff0c;详细参考&#xff1a;微信公众平台 Redis 保证数据不丢失的主要手段有两个&#xff1a; 持久化 多机部署 我们分别来看它们两的具体实现细节。 1.Redis 持久化 持久化是指将数据从内存中存储到持久化存储介质中&#xff08;如硬盘&#xf…

STM32F405RGT6单片机原理图、PCB免费分享

大学时机创比赛时画的板子&#xff0c;比到一半因为疫情回家&#xff0c;无后续&#xff0c;&#xff0c;&#xff0c;已打板验证过&#xff0c;使用stm32f405rgt6做主控 下载文件资源如下 原理图文件 pcb文件 外壳模型文件 stm32f405例程 功能 以下功能全部验证通过 4路…

“穿梭于容器之间:C++ STL迭代器的艺术之旅”

引言&#xff1a; 迭代器&#xff08;Iterator&#xff09;是C STL&#xff08;标准模板库&#xff09;中非常重要的一部分&#xff0c;它提供了一种统一的方式来遍历容器中的元素。无论容器是数组、链表、树还是其他数据结构&#xff0c;迭代器都能够以一致的方式访问这些数据…

jmeter常用配置元件介绍总结之用linux服务器压测

系列文章目录 安装jmeter jmeter常用配置元件介绍总结之用linux服务器压测 1.编写测试脚本2.执行测试脚本 1.编写测试脚本 在linux服务器上进行压测&#xff0c;由于是没有界面的&#xff0c;因此我们可以先在界面上把压测脚本写好&#xff1a; 如图&#xff1a;我这里简单的写…