[LeetCode]Max Consecutive Ones II

有好几种解法，首先DP可以做。因为我们每翻转一个0，之后整个长度取决于左边和右边1的数量，我们可以记录每个0左边和右边的1的长度，最后取相加最大。时间空间复杂度都是O(n)，代码如下：

	class Solution {
	public:
	int findMaxConsecutiveOnes(vector<int>& nums) {
	int len = nums.size(), count = 0;
	vector<int> dp(len, 0);
	for(int i = 0; i < len; ++i)
	{
	if(nums[i])
	++count;
	else
	{
	dp[i] = count;
	count = 0;
	}
	}
	if(count == len)return len;
	count = 0;
	int maxLen = 0;
	for(int i = len - 1; i >= 0; --i)
	{
	if(nums[i])
	++count;
	else
	{
	dp[i] +=count;
	count = 0;
	maxLen = max(maxLen, dp[i]);
	}
	}
	return maxLen + 1;
	}
	};

view raw Max Consecutive Ones II_1.cpp hosted with ❤ by GitHub

那么如果我们generalize这个问题，翻转k个0之后的最大长度。我们显然无法用DP。我们考虑其他的方法，假设我们将整个数组翻转，0变成1，1变成0，在求出presum数组。presum数组每加1一次，就代表原数组位置为0，如果我们允许k个0，也就是把问题转化为，presum数组差等于k的最长的subarray（presum数组一定是递增的）。我们把所有差等k的求出来就行了，时间复杂度O(n)，空间复杂度O(n)，代码如下：

	class Solution {
	public:
	int findMaxConsecutiveOnes(vector<int>& nums) {
	return flipK(nums, 1);
	}
	private:
	int flipK(vector<int>& nums, int k)
	{
	int len = nums.size(), count = 0;
	for(auto& num : nums)
	{
	if(num)
	num = 0;
	else
	{
	++count;
	num = 1;
	}
	}
	if(count <= k)return len;
	for(int i = 1; i < len; ++i)
	nums[i] += nums[i - 1];
	nums.emplace_back(nums[len - 1] + 1);
	unordered_map<int, int> map;
	map[0] = -1;
	int maxLen = 0;
	for(int i = 0; i < len + 1; ++i)
	{
	if(map.find(nums[i]) == map.end())
	{
	if(nums[i] > k)
	{
	int currLen = i - map[nums[i] - (k + 1)] - 1;
	maxLen = max(maxLen, currLen);
	}
	map[nums[i]] = i;
	}
	}
	return maxLen;
	}
	};

view raw Max Consecutive Ones II_2.cpp hosted with ❤ by GitHub

如果我们在进一步generalize，数组中可以存在任何数，翻转k个0之后的最长连续不为零子区间。我们没法用presum了。从左到右遍历，每次更新右边界，同时我们用queue保存所有0的位置，并且记录左边界，当queue的size大于k之后，我们更新左边界为queue.front() + 1即可，这个区间还是满足只有k个0的条件。然后我们记录最大值，类似two pointer的解法。时间复杂度O(n)，空间复杂度O(k)，代码如下：

	class Solution {
	public:
	int findMaxConsecutiveOnes(vector<int>& nums) {
	return flipK(nums, 1);
	}
	private:
	int flipK(vector<int>& nums, int k)
	{
	int len = nums.size(), i = 0, maxLen = 0, lo = 0;
	queue<int> zeros;
	while(i < len)
	{
	if(!nums[i])
	zeros.push(i);
	if(zeros.size() > k)
	{
	lo = zeros.front() + 1;
	zeros.pop();
	}
	maxLen = max(maxLen, i - lo + 1);
	++i;
	}
	return maxLen;
	}
	};

view raw Max Consecutive Ones II_3.cpp hosted with ❤ by GitHub