【滑动窗口】【差分数组】C++算法：K 连续位的最小翻转次数

作者推荐

动态规划多源路径字典树 LeetCode2977:转换字符串的最小成本

本题涉及知识点

滑动窗口差分数组

LeetCode995: K 连续位的最小翻转次数

给定一个二进制数组 nums 和一个整数 k 。
k位翻转就是从 nums 中选择一个长度为 k 的子数组，同时把子数组中的每一个 0 都改成 1 ，把子数组中的每一个 1 都改成 0 。
返回数组中不存在 0 所需的最小 k位翻转次数。如果不可能，则返回 -1 。
子数组是数组的连续部分。
示例 1：
输入：nums = [0,1,0], K = 1
输出：2
解释：先翻转 A[0]，然后翻转 A[2]。
示例 2：
输入：nums = [1,1,0], K = 2
输出：-1
解释：无论我们怎样翻转大小为 2 的子数组，我们都不能使数组变为 [1,1,1]。
示例 3：
输入：nums = [0,0,0,1,0,1,1,0], K = 3
输出：3
解释：
翻转 A[0],A[1],A[2]: A变成 [1,1,1,1,0,1,1,0]
翻转 A[4],A[5],A[6]: A变成 [1,1,1,1,1,0,0,0]
翻转 A[5],A[6],A[7]: A变成 [1,1,1,1,1,1,1,1]
参数范围：
1 <= nums.length <= 10⁵
1 <= k <= nums.length

滑动窗口+差分数组

时间复杂度 O(n)。
如果nums中不存在0，则直接返回0。
令nums[i1]等于0，如果有多个符合的i1，取最小值。设某次翻转[i,i+k)，则i的最小值一定为i1。且一定只翻转一次。
翻转奇数次和翻转一次的效果完全一样，所以不需要翻转1以外的奇数次。
翻转偶数次，和没翻转效果一样。所以没必要翻转偶数次。


i < i1	翻转一次后nums[i]变成0，不符合题意
i>i1	nums[i1]为0，不符合题意

翻转i1后，类似原理处理nums[i1+1…]，直到处理完毕。

差分数组

翻转[i,i+len)不需要修改nums[i,i+k)的值，那样的时间复杂度是O(k)。修改vDiff[i]++,vDiff[i+len]-- 就可以了。
i的翻转次数就是vDiff[0,i]之和。差分数组单个修改的时间复杂为O(1)。

只能翻转k次，不能翻转k-1次

即i+len <= n 。最后的k-1个元素无法翻转。

代码

核心代码

class Solution {
public:
	int minKBitFlips(vector<int>& nums, int k) {
		m_c = nums.size();
		vector<int> vDiff(m_c+1);
		int iRet = 0;
		int iDiff = 0;
		int i = 0;
		for (; i+k-1 < m_c; i++)
		{
			iDiff += vDiff[i];
			int n = (nums[i] + iDiff) % 2;
			if (0 == n)
			{
				iRet++;
				iDiff++;
				vDiff[i + k]--;
			}
		}
		for (; i  < m_c; i++)
		{
			iDiff += vDiff[i];
			int n = (nums[i] + iDiff) % 2;
			if (0 == n)
			{
				return -1;
			}
		}
		return iRet;
	}
	int m_c;
};

测试用例

template<class T>
void Assert(const T& t1, const T& t2)
{
	assert(t1 == t2);
}

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
	if (v1.size() != v2.size())
	{
		assert(false);
		return;
	}
	for (int i = 0; i < v1.size(); i++)
	{
		Assert(v1[i], v2[i]);
	}
}


int main()
{
	vector<int> nums = { 1, 2, 1, 2, 3 };
	int k = 2;
	{
		Solution sln;
		nums = { 0,1,0 }, k = 1;
		auto res = sln.minKBitFlips(nums, k);
		Assert(2, res);
	}
	{
		Solution sln;
		nums = { 1,1,0 }, k = 2;
		auto res = sln.minKBitFlips(nums, k);
		Assert(-1, res);
	}
	{
		Solution sln;
		nums = { 0,0,0,1,0,1,1,0 }, k = 3;
		auto res = sln.minKBitFlips(nums, k);
		Assert(3, res);
	}
}

2023年3月版

class Solution {
public:
int minKBitFlips(vector& nums, int k) {
m_c = nums.size();
//差分数组
vector v(m_c);
int iVTotal = 0;
int iRet = 0;
for (int i = 0; i < m_c; i++)
{
iVTotal += v[i];
const int iCur = (nums[i] + iVTotal)%2 ;
if (0 == iCur)
{
if (i + k > m_c)
{
return -1;
}
v[i]++;
if (i + k != m_c)
{
v[i + k]–;
}
iVTotal++;
iRet++;
}
}
return iRet;
}
int m_c;
};

2023年7月版

class Solution {
public:
int minKBitFlips(vector& nums, int k) {
m_c = nums.size();
vector vDiff(m_c + 1);
int iRotaNum = 0;
int iRota = 0;
for (int i = 0; i < m_c; i++)
{
iRota += vDiff[i];
const int iCur = (0 == iRota % 2) ? nums[i] : (1 - nums[i]);
if (1 == iCur )
{
continue;
}
const int iEnd = i + k;
if (iEnd > m_c)
{
return -1;
}
iRotaNum++;
iRota++;
vDiff[i]++;
vDiff[iEnd]++;
}
return iRotaNum;
}
int m_c;
};

扩展阅读

视频课程

有效学习：明确的目标及时的反馈拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛