leetcode 1004. 最大连续1的个数 III(优质解法)

代码:

class Solution {
    public int longestOnes(int[] nums, int k) {
        int length=nums.length;
        int zero=0; //计数器,计数翻转 0 的个数
        int max=0;  //记录当前获得的最长子数组长度
        for(int left=0,right=0;right<length;right++){
           if(nums[right]==0){
               zero++;
               while (zero>k){
                   if(nums[left]==0){
                       zero--;
                   }
                   left++;
               }
               //zero<=k
           }
           //nums[right]==1
            max=Math.max(max,right-left+1);
        }
        return max;
    }
}

题解:

        首先,我们可以思考一下这个题的题意,题目要求找到数组中连续 1 的最大个数,由于需要连续的数据,说明需要我们找到的是连续 1 的 “子数组” ,而存在翻转 0 的机制,所以我们找到的子数组中最大可容纳 k 个 0 

        那么我们可以想到这个题的暴力解法,就是遍历获得所有的子数组,去除掉含 k 个 0 以上的子数组,在剩余的子数组中找到长度最长的子数组

        关于子数组以及子串的问题,我们很容易想到通过滑动窗口 - 双指针的方式解决

        我们通过示例 1 来进行分析:nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2        

        将指针 L 和 R 指向 下标 0 的位置,L 和 R 指针之间的数据便是我们此时要讨论的子数组,首先,判断 R 指针指向的数据,数据为 1 ,那么此时我们不需要进行字符翻转,记录当前子数组的长度,让 R++ ,扩大我们讨论的子数组长度

1        1        1        0        0        0        1        1        1        1        0

R

        当 R 指针指向 1 ,我们只需要和上述条件一样,记录当前子数组的长度(当前长度与之前保存的长度进行比较,取较大的保存),让 R++ ,扩大我们讨论的子数组长度即可,一直扩大到 R 指针指向 0 

        此时我们讨论的子数组中出现 0 了,但题目有字符翻转的机制,所以我们可以将当前遇到的 0 翻转为 1,我们通过一个计数器 zero ,记录我们已经翻转的 0 的个数,此时 zero = 1 (不会有小可爱真的把源数据改为 1 把),只有 zero > k 时才代表我们已经不能进行翻转,将 0 翻转为 1 后,我们同样记录当前讨论的子数组的长度,再让 R++ ,继续扩大我们讨论的子数组长度 

1        1        1        0        0        0        1        1        1        1        0

                              R 

        当 R 指针指向当前位置时,计数器 zero 中的值为 3 ,已经大于 k 了,所以 R 指针此时指向的 0 ,我们不能进行翻转,这也代表以 L 指针为首位的子数组的最长长度我们已经获得了,此时我们可以让 L ++ ,讨论以下一个元素为首位的子数组的最长长度

1        1        1        0        0        0        1        1        1        1        0

                                                   R    

        现在出现一个问题,我们需要让 R 指针回到 L 指针的位置,从头开始讨论子数组的最长长度吗?答案是不需要,因为 R 指针到达当前位置,0 的个数才增多,子数组才不符合要求,这也代表,R 指针之前的数据都是符合要求的,即使我们让 R 指针回到 L 指针的位置从头开始讨论,R 指针也一定会移动到当前位置,所以没有必要让 R 指针回去,此时 zero =3 不符合要求,我们让 L ++ 直到符合要求为止

1        1        1        0        0        0        1        1        1        1        0

          L         

                                                   R

        当 L 指针移动到当前位置时,zero = 2 = k,符合要求,记录当前讨论的子数组的长度,就可以让 R ++,继续扩大我们讨论的子数组长度 

1        1        1        0        0        0        1        1        1        1        0

                                        L         

                                                   R

        接下来的操作就是循环,直到 R 指针移动到当前位置,R = nums.length,就结束循环,得到了最长的子数组长度

1        1        1        0        0        0        1        1        1        1        0

                                                   L      

                                                                                                            R

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

vsftpd.confg 常用配置,Beyond Compare 测试可用

vsftpd.confg 常用配置,备份一下, 经常配置好久 , 以后直接粘贴即可. Beyond Compare 测试可用. # Example config file /etc/vsftpd.conf # # The default compiled in settings are fairly paranoid. This sample file # loosens things up a bit, to make the ftp daemon m…

使用有道词典复制网页上的字

1. 今天发现一个新大陆&#xff0c;同事教的&#xff0c;有道词典可以复制网页上的字&#xff0c;也可以复制PDF文件等一些限制不可复制的字&#xff0c;原来不可复制的字&#xff0c;现在用有道都可以复制了&#xff0c;不需要用油猴下载脚本了。写给老婆这种纯电脑小白的。其…

销售人员如何自我提升?

销售人员如何自我提升&#xff1f; 在美国有这么一句流行语&#xff1a;不当总统就干销售员。其实在国内很多老板&#xff0c;高收入人群等大部分是来自销售岗位。因为销售是离钱最近的职业&#xff0c;在销售职业生涯中能收获到很多&#xff0c;比如人际关系能力&#xff0c;…

使用Scanner扫描器和if语句来判断QQ等级的活跃程度

一、主要特点 总体使用try包围起来&#xff0c;用到了Scanner扫描器&#xff0c;还用到了若干if语句。 二、运行代码 import java.util.Scanner; public class QQtest {public static void main(String[] args){try (Scanner scan new Scanner(System.in)) {System.out.pr…

【C语言】mmap函数

mmap是一种在Unix/Linux操作系统中将文件映射到进程的地址空间的方法&#xff0c;它允许程序像访问内存一样访问文件。这种方法可以提高文件访问的速度和效率&#xff0c;特别是对于大文件而言。 以下是mmap的基本使用方法&#xff1a; 1. 包含头文件&#xff1a; 在使用mma…

预览控制;预见控制;预测控制;预观控制(preview control)

预演控制&#xff08;preview control&#xff09;作为一种新兴的控制方法&#xff0c;首次在轮式车辆中被提出。 参考文献&#xff1a; https://www.sciencedirect.com/science/article/pii/S0016003219300390https://www.sciencedirect.com/science/article/pii/S0016003219…

消息队列zookeeper集群+kafka

消息队列zookeeper集群kafka kafka 3.0之前依赖于zookpeeper zookeeper开源分布式架构&#xff0c;提供协调服务&#xff08;Apache项目&#xff09; 基于观察者模式设计的分布式服务管理架构 存储和管理数据。分布式节点的服务结束观察者的注册&#xff0c;一旦分布式节点…

【WPF 按钮点击后异步上传多文件code示例】

前言: WPF中按钮点击事件如何执行时间太长会导致整个UI线程卡顿&#xff0c;现象就是页面刷新卡住&#xff0c;点击其他按钮无反馈。如下是进行异步执行命令&#xff0c;并远程上传文件的代码。 // 这里对于长时间执行的任务&#xff0c;必须使用异步方法进行处理private async…

HomeAssistant如何添加HACS插件实现公网控制米家与HomeKit等智能家居

HomeAssistant添加HACS插件并实现公网控制米家&#xff0c;HomeKit等智能家居 文章目录 HomeAssistant添加HACS插件并实现公网控制米家&#xff0c;HomeKit等智能家居基本条件一、下载HACS源码二、添加HACS集成三、绑定米家设备 ​ 上文介绍了如何实现群晖Docker部署HomeAssist…

【算法系列篇】递归、搜索与回溯(一)

文章目录 什么是递归、搜索与回溯算法1. 汉诺塔1.1 题目要求1.2 做题思路1.3 代码实现 2. 合并两个有序链表2.1 题目要求2.2 做题思路2.3 代码实现 3. 反转链表3.2 题目要求3.2 做题思路3.3 代码实现 什么是递归、搜索与回溯算法 递归算法是一种通过重复将问题分解为同类的子问…

是宝箱还是潘朵拉魔盒?ChatGPT正在悄然改变世界...

2022年11月30日&#xff0c;OpenAI推出了一款全新的对话式通用人工智能工具——ChatGPT。与以往的人工智障不同&#xff0c;ChatGPT能够与用户进行自然、流畅的对话&#xff0c;帮助人们解答各种问题&#xff0c;提供所需的帮助和支持。 据报道&#xff0c;ChatGPT在推出短短几…

技术阅读周刊第第8️⃣期

技术阅读周刊&#xff0c;每周更新。 历史更新 20231103&#xff1a;第四期20231107&#xff1a;第五期20231117&#xff1a;第六期20231124&#xff1a;第七期 Prometheus vs. VictoriaMetrics (VM) | Last9 URL: https://last9.io/blog/prometheus-vs-victoriametrics/?refd…

中碳CCNG:碳交易领域的革命者

在全球碳减排努力日益增强的背景下&#xff0c;中国碳中和发展集团有限公司&#xff08;简称中碳CCNG&#xff09;正以其创新的碳交易平台引领行业新趋势。中碳CCNG提供的一站式综合服务不仅包括碳信用的托管、买卖和抵消&#xff0c;而且通过其综合性数字平台&#xff0c;促进…

Mysql- 流程函数-(If, CASE WHEN)的使用及练习

目录 4.1 If函数语法格式 4.2 CASE WHEN 条件表达式格式 4.3 练习题1 4.4 练习题2 4.5 练习题3-行转列 4.6 牛客练习题 4.7 LeetCode练习题 4.1 If函数语法格式 IF(expr1,expr2,expr3) 解释&#xff1a; 如果表达式expr1true(expr1 <> 0 and expr1 <> NUL…

element-plus组件中的el-drawer的使用

在项目的制作过程中经常会用到弹窗组件&#xff0c;这里假设一种情况当你在一个页面需要多个弹窗组件的时候怎么样才能精准的打开和关闭对应的弹窗呐&#xff1f;&#xff1f; ① 绑定一个点击事件----【给点击事件传入一个下标】这里是打开事件 ② 使用element-plus中的 :befo…

Redis系列之keys命令和scan命令性能对比

项目场景 Redis的keys *命令在生产环境是慎用的&#xff0c;特别是一些并发量很大的项目&#xff0c;原因是Redis是单线程的&#xff0c;keys *会引发Redis锁&#xff0c;占用reids CPU&#xff0c;如果key数量很大而且并发是比较大的情况&#xff0c;效率是很慢的&#xff0c…

ActiveMQ 反序列化漏洞(CVE-2015-5254)

ActiveMQ 反序列化漏洞 Apache ActiveMQ是一种开源的消息代理&#xff08;message broker&#xff09;&#xff0c;被广泛用于应用程序之间的消息传递。它提供可靠的消息传递模式&#xff0c;如发布/订阅、点对点和请求/响应&#xff0c;非常适合构建分布式系统和应用程序集成…

感觉到自己思想扭曲了

突然觉得自己思想有点扭曲。 ​起因是近期备婚&#xff0c;需要给男方家人买衣服。问男朋友妹妹衣服预算多少&#xff0c;说是500内&#xff0c;然后想想自己这个新娘子&#xff0c;那一身衣服绞尽脑汁凑满减不到300。再联想到装饰新房&#xff0c;新房买家具&#xff0c;为了省…

为 3D 模型制作纹理的 9 种最佳方法

在线工具推荐&#xff1a; 3D数字孪生场景编辑器 - GLTF/GLB材质纹理编辑器 - 3D模型在线转换 - Three.js AI自动纹理开发包 - YOLO 虚幻合成数据生成器 - 三维模型预览图生成器 - 3D模型语义搜索引擎 与普遍的看法相反&#xff0c;3D 模型的纹理创建更加简单。虽然对细节…

【PyQt学习篇 · ⑫】:QVBoxLayout和QHBoxLayout布局管理器的使用

文章目录 QVBoxLayout和QHBoxLayout的介绍.addStretch()的使用方法.setSpacing()方法的使用.setAlignment()的使用.setFixedSize()的使用QMainWindow中使用布局管理器 QVBoxLayout和QHBoxLayout的介绍 QVBoxLayout 和 QHBoxLayout 是 PyQt 中用于实现垂直和水平布局的两个布局…