C++で配列を美しくするために必要な最小限の操作を見つける

この問題では、たまたま0と1であるn個のバイナリ値で構成されるバイナリ配列bin []が与えられます。私たちのタスクは、配列を美しくするために必要な最小限の操作を見つけることです。

美しい配列は、0と1が交互に現れるパターンで構成される特殊なタイプのバイナリ配列です。

問題の説明 −配列を美しくするために必要な演算の数を見つける必要があります。操作はこれらのステップで構成されます-

ステップ1 −アレイを2つに分割します。

ステップ2 −2つの半分のいずれかを逆にします。

ステップ3 −参加してから半分に戻ります。

配列が美しい配列になるようにするために必要な操作の数をカウントします。

問題を理解するために例を見てみましょう

入力

bin[] = {1, 0, 1, 0, 0, 1}

出力

1

説明

配列を切り取り、サブ配列bin [4、5]を作成し、逆にして結合します。

ソリューションアプローチ

この問題の解決策は、連続するゼロの数に等しいスイッチ操作の最小数を見つけることに基づいています。基本ケースは-

配列のサイズが1の場合、それは美しい配列です。配列のサイズが奇数の場合、美しい配列になることはありません。

すべての偶数の長さについて、実行される操作の数となる連続するゼロまたは1の総数をチェックします。

アルゴリズム

初期化-zeroCount、oneCount、consZero =0

ステップ1 −（n =1）の場合、0を返します

ステップ2 −（n％2！=0）の場合、-1を返します。

ステップ3 −ループfori->0からn-1。

ステップ3.1 − bin [i] ==bin [i + 1] ==0の場合、consZero++。

ステップ4 − bin [n-1] ==bin [0] ==0の場合、consZero++。

ステップ5 −consZeroを返します。

ソリューションの動作を説明するプログラム

例

#include <iostream>
using namespace std;
int minOperations(int bin[], int n) {
   if(n == 1)
      return 0;
   if(n%2 != 0)
      return -1;
      int consZero = 0;
   for (int i = 0; i < n; ++i) {
      if (i + 1 < n) {
         if (bin[i] == 0 && bin[i + 1] == 0)
            consZero++;
      }
   }
   if (bin[0] == bin[n - 1] && bin[0] == 0)
      consZero++;
      return consZero;
}
int main() {
   int bin[] = { 1, 0, 1, 0, 0, 1};
   int n = sizeof(bin) / sizeof(bin[0]);
   cout<<"The minimum operations needed to make an Array beautiful is "<<minOperations(bin, n);
   return 0;
}

出力

The minimum operations needed to make an Array beautiful is 1