Max Consecutive Ones I & II
in LeetCode with 0 comment

Max Consecutive Ones I & II

in LeetCode with 0 comment
最大连续1的个数,以及 带翻转的最大连续1的个数

最大连续1的个数

题目链接:https://leetcode.com/problems/max-consecutive-ones

这是个签到题,就不浪费时间描述了

class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        int temp_max = 0, all_max = 0;
        for (int p : nums) {
            if (p)
                temp_max++;
            else {
                all_max = max(all_max, temp_max); 
                temp_max = 0;
            }
        }
        return max(all_max, temp_max);
    }
};

带翻转的最大连续1的个数

这个题是美团的笔试题,不过跟leetcode上的 https://leetcode.com/problems/max-consecutive-ones-ii 是一个路子,而且这道题目竟然还要钱...

我们可以维护一个窗口[left,right]来容纳至少k个0。

我们遇到了0,就累加zero的个数,

然后判断如果此时0的个数大于k,那么我们我们右移左边界left,

如果移除掉的nums[left]为0,那么我们zero自减1。

如果不大于k,那么我们用窗口中数字的个数来更新res,参见代码如下:

k 就是最多可以翻转的次数

class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums,int k) {
        int res = 0, zero = 0, left = 0;
        for (int right = 0; right < nums.size(); ++right) {
            if (nums[right] == 0) ++zero;
            while (zero > k) {
                if (nums[left++] == 0) --zero;
            }
            res = max(res, right - left + 1);
        }
        return res;
    }
};

举个例子: [1,0,0,1,0,1,0,1]

窗口大小是k,这里取2

[{1,0,0,1},0,1,0,1]

又发现了一个0,所以left++ ,直到移除掉nums[left]的0,其实就是为了保证窗口内有两个0
[1,0,{0,1,0},1,0,1]

[1,0,0,{1,0,1,0,1}]

Responses

From now on, bravely dream and run toward that dream.
陕ICP备17001447号