C++でのK個の連続するビットフリップの最小数

配列Aがあるとします。これには0と1のみが含まれます。ここで、Kビットフリップは、長さKの（連続した）サブ配列を選択し、同時にサブ配列のビットを反転することで構成されます。配列に0がないように、必要なKビットフリップの最小数を見つける必要があります。そのような可能性がない場合は、-1を返します。

したがって、入力が[0,0,0,1,0,1,1,0]のようで、K =3の場合、最初の試行で3回操作を実行する必要があるため、出力は3になります。 A[0]をA[3]にフリップすると、配列は[1,1,1,1,0,1,1,0]になり、2回目の実行ではA[4]をA[6]にフリップします。 [1,1,1,1,1,0,0,0]になり、3番目の移動でA[5]をA[7]に変更すると、配列は[1,1,1,1,1]になります。 、1,1,1]。

これを解決するには、次の手順に従います-

• n：=Aのサイズ

• サイズnの配列移動を定義する

• カウンター：=0

• 初期化i：=0の場合、i + K <=nの場合、更新（iを1増やします）、実行-

  • i> 0の場合、-

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

  • そうでない場合（（moves [i] mod 2）+ A [i]）mod 2がゼロ以外の場合、-

    • moves [i]：=moves [i] + 1

    • i + K

      • 移動[i+K]-=1

    • （カウンターを1増やします）

• i

  • i> 0の場合、-

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

  • そうでない場合（（moves [i] mod 2）+ A [i]）mod 2がゼロ以外の場合、-

    • -1を返す

• リターンカウンター

理解を深めるために、次の実装を見てみましょう-

出力

#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