485.Max Consecutive Ones I & II

最大连续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}]