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] mod 2）+ A [i]）mod 2不为零，则-

• 对于i <n，更新（i增加1），做-

• 返回-1

• 移动[i]：=移动[i] +移动[i-1]

• 如果i> 0，则-

• 如果不是（（moves [i] mod 2）+ A [i]）mod 2不为零，则-

• 返回柜台

让我们看下面的实现以更好地理解-

输出结果

#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