您现在的位置是:首页 > 正文

C++描述 LeetCode 1004. 最大连续1的个数 III

2024-02-01 06:47:50阅读 2

C++描述 LeetCode 1004. 最大连续1的个数 III

  大家好,我叫亓官劼(qí guān jié ),在CSDN中记录学习的点滴历程,时光荏苒,未来可期,加油~博主目前仅在CSDN中写博客,唯一博客更新的地址为:亓官劼的博客 ,同时正在尝试在B站中做一些内容分享,B站主页为: 亓官劼的B站主页

本文原创为亓官劼,请大家支持原创,部分平台一直在恶意盗取博主的文章!!!
若需联系博主,可以联系本人微信:qiguanjie2015


给定一个由若干 01 组成的数组 A,我们最多可以将 K 个值从 0 变成 1 。

返回仅包含 1 的最长(连续)子数组的长度。

示例 1:

输入:A = [1,1,1,0,0,0,1,1,1,1,0], K = 2
输出:6
解释: 
[1,1,1,0,0,1,1,1,1,1,1]
粗体数字从 0 翻转到 1,最长的子数组长度为 6。

示例 2:

输入:A = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
输出:10
解释:
[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
粗体数字从 0 翻转到 1,最长的子数组长度为 10。

提示:

  1. 1 <= A.length <= 20000
  2. 0 <= K <= A.length
  3. A[i]01

解题思路

滑动窗口。设置左右指针l和r分别指向当前区间的左右边界,使用lsum记录0-l中0的个数,rsum记录0-r中0的个数,则rsum-lsum表示当前区间内0的个数,如果rsum - lsum - K <= 0则说明当前区间内都可以转为1,更新res,否则l右移,更新lsum即可

算法实现

class Solution {
public:
    int longestOnes(vector<int>& A, int K) {
        int res = 0, len = A.size();
        // lsum记录0-l中0的个数,rsum记录0-r中0的个数
        int lsum = 0, rsum = 0, l = 0;
        for(int r = 0; r < len ; r++){
            rsum = rsum + 1 - A[r];
            while(rsum - lsum - K > 0){
                // 当前区间有多余的0时,l右移
                lsum = lsum + 1 - A[l++];
            }
            res = max(res,r-l+1);
        }
        return res;
    }
};

网站文章

  • 【实战】阿里云https证书申请与部署

    【实战】阿里云https证书申请与部署

    文章目录阿里云https证书申请与部署1.证书申请2.证书部署 阿里云https证书申请与部署 1.证书申请 登录阿里云官网:https://www.aliyun.com/ 搜索ssl,点进第一个搜索结果 滑到底 选择免费证书,点击购买 再次点击立即购买 去支付 确认支付 支付成功,返回证书控制台 未签发栏下点击证书申请 填写申请需要的相关内容,点击下一步: 进行信息验证(上面...

    2024-02-01 06:47:43
  • 为什么要反弹shell

    我也不知道这个比喻恰不恰当:首先是一个城池,我想要控制这个城,就要控制这个城的城主,我手里有控制当前城主的把柄(shell)但是我要和城主建立起联系才可以控制他,城外有一座大墙(防火墙),会严格检查入...

    2024-02-01 06:47:12
  • 0202性能分析-索引-MySQL

    0202性能分析-索引-MySQL

    0202性能分析-索引-MySQL

    2024-02-01 06:47:06
  • 傅里叶变换,其物理意义是什么?(转)

    1、为什么要进行傅里叶变换,其物理意义是什么?傅立叶变换是数字信号处理领域一种很重要的算法。要知道傅立叶变换算法的意义,首先要了解傅立叶原理的意义。傅立叶原理表明:任何连续测量的时序或信号,都可以表示为不同频率的正弦波信号的无限叠加。而根据该原理创立的傅立叶变换算法利用直接测量到的原始信号,以累加方式来计算该信号中不同正弦波信号的频率、振幅和相位。和傅立叶变换算法对应的是反傅立

    2024-02-01 06:46:58
  • (python)诗词排版(横排)

    完成了数据输入,其中poem存储了一首诗(无标点),n可能是5或者7,代表poem是五言诗或者七言诗。此代码可以帮助新手更加直观地认识python的作用。ju 代表的是本诗一共有多少句。利用for循环进行排版。

    2024-02-01 06:46:51
  • 轻松模拟数据库

    测试驱动的开发真是太好了! 在组织中建立它之后,您将开始: 极大地提高您的质量(事情不常发生) 大大改善您的流程(事情可以更轻松地更改) 极大地改善您的开发人员氛围(事情更有趣) 进行正确的测试驱动开发的重要性是找到要覆盖的代码的良好比例。 通过自动单元测试 通过自动集成测试 通过手动“烟雾测试” 通过手动的“验收测试” 一点也不 找到该比例可...

    2024-02-01 06:46:20
  • Ubuntu20.04 安装 ROS2

    官方文档

    2024-02-01 06:46:13
  • 计算机断网后显示配置0%,电脑断网后自动报警提醒怎么设置

    很多小伙伴经常开着电脑在互联网上下载各种资料,大型软件、高清电影等等。但是这年头有些网络运营商经常各种不靠谱,带宽偷工减料不说,还时不时断网。于是经常出现这样一幕场景:1、打开电脑附件的命令提示符窗口...

    2024-02-01 06:46:06
  • 【Leetcode刷题】哈希

    【Leetcode刷题】哈希

    Leetcode1.两数之和、Leetcode290.单词规律、Leetcode594.最长和谐子序列、Leetcode17.电话号码的字母组合、Leetcode49.字母异位词分组、Leetcode...

    2024-02-01 06:45:36
  • chatgpt赋能Python-python_crc校验

    本文由chatgpt生成,文章没有在chatgpt生成的基础上进行任何的修改。以上只是chatgpt能力的冰山一角。作为通用的Aigc大模型,只是展现它原本的实力。对于颠覆工作方式的ChatGPT,应...

    2024-02-01 06:45:28