C ++中K个连续位翻转的最小数目
假设我们有一个数组A。它只包含0和1，这里的K位翻转包括选择一个长度为K的（连续）子数组，同时将子数组中的位取反。我们必须找到所需的最小K位翻转次数，以便数组中不存在0。如果没有这种可能性，则返回-1。
因此，如果输入像[0,0,0,1,0,1,1,0]且K=3，则输出将为3，因为我们需要在第一次尝试中执行三次运算将A[0]翻转为A[3]，则数组将为[1,1,1,1,0,1,1,0]，第二次运行将A[4]翻转为A[6]将为[1,1,1,1,1,0,0,0]，在第三步将A[5]更改为A[7]时，数组将为[1,1,1,1,1,,1,1,1]。
为了解决这个问题，我们将遵循以下步骤-
n：=A的大小
定义大小为n的数组移动
计数器：=0
对于初始化i：=0，当i+K<=n时，更新（将i增加1），执行-
移动[i]：=移动[i]+1
如果i+K<n，则-
（将计数器增加1）
移动[i+K]-=1
移动[i]：=移动[i]+移动[i-1]
如果i>0，则-
如果不是（（moves[i]mod2）+A[i]）mod2不为零，则-
对于i<n，更新（i增加1），做-
返回-1
移动[i]：=移动[i]+移动[i-1]
如果i>0，则-
如果不是（（moves[i]mod2）+A[i]）mod2不为零，则-
返回柜台
让我们看下面的实现以更好地理解-
输出结果
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minKBitFlips(vector<int>& A, int K){
int n = A.size();
vector<int> moves(n);
int i;
int counter = 0;
for (i = 0; i + K <= n; i++) {
if (i > 0)
moves[i] += moves[i - 1];
if (!(((moves[i] % 2) + A[i]) % 2)) {
moves[i] += 1;
if (i + K < n)
moves[i + K] -= 1;
counter++;
}
}
for (; i < n; i++) {
if (i > 0)
moves[i] += moves[i - 1];
if (!(((moves[i] % 2) + A[i]) % 2))
return -1;
}
return counter;
}
};
main(){
Solution ob;
vector<int> v = {0,0,0,1,0,1,1,0};
cout << (ob.minKBitFlips(v, 3));
}输入项
{0,0,0,1,0,1,1,0}, 3输出结果
3