​LeetCode刷题实战487:最大连续1的个数 II

程序IT圈

共 1354字,需浏览 3分钟

 ·

2022-01-09 20:52

算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !

今天和大家聊的问题叫做 最大连续1的个数 II,我们先来看题面:
https://leetcode-cn.com/problems/max-consecutive-ones-ii/

Given a binary array, find the maximum number of consecutive 1s in this array if you can flip at most one 0.

给定一个二进制数组,你可以最多将 1 个 0 翻转为 1,找出其中最大连续 1 的个数。

示例                         

输入:[1,0,1,1,0]
输出:4
解释:翻转第一个 0 可以得到最长的连续 1。
     当翻转以后,最大连续 1 的个数为 4。


解题


这道题在之前那道题 Max Consecutive Ones 的基础上加了一个条件,说有一次将0翻转成1的机会,问此时最大连续1的个数,再看看 follow up 中的说明,很明显只遍历一次数组,那我们想,肯定需要用一个变量 cnt 来记录连续1的个数吧,那么当遇到了0的时候怎么处理呢,因为有一次0变1的机会,所以遇到0了还是要累加 cnt,然后此时需要用另外一个变量 cur 来保存当前 cnt 的值,然后 cnt 重置为0,以便于让 cnt 一直用来统计纯连续1的个数,然后我们每次都用用 cnt+cur 来更新结果 res,参见代码如下:

class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        int res = 0, cur = 0, cnt = 0;
        for (int num : nums) {
            ++cnt;
            if (num == 0) {
                cur = cnt;
                cnt = 0;
            }
            res = max(res, cnt + cur);
        }
        return res;
    }
};


好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力 。

上期推文:

LeetCode1-480题汇总,希望对你有点帮助!

LeetCode刷题实战481:神奇字符串

LeetCode刷题实战482:密钥格式化

LeetCode刷题实战483:最小好进制

LeetCode刷题实战484:寻找排列

LeetCode刷题实战485:最大连续 1 的个数

LeetCode刷题实战486:预测赢家



浏览 16
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报