C ++で連続する1の数が最大になるように、反転するゼロを見つけます

このチュートリアルでは、配列内の連続する1の最大数を取得するために反転する必要のあるゼロカウントを見つけます。

この問題を解決するために、スライディングウィンドウアプローチを使用します。問題を解決するための手順を見てみましょう。

• 反転する配列と最大ゼロを初期化します。

• ウィンドウの開始インデックスと終了インデックスを長さとともに初期化します。

• 連続する1の長さと開始インデックスの最大サブ配列を格納します。

• 終了インデックスが配列の長さを超えるまで、配列を繰り返し処理します。

• ゼロの数が最大のゼロの数よりも少ない場合は、終了インデックスをインクリメントし、現在の値がゼロの場合はゼロの数を増やします。

• ゼロの数が最大のゼロの数よりも大きい場合は、開始インデックスをインクリメントし、現在の値がゼロの場合はゼロの数を減らします。

• 現在のウィンドウの長さが前のウィンドウの長さよりも長い場合は、最大ウィンドウを更新します。

• 配列を反復処理し、ウィンドウ開始インデックスを使用してゼロインデックスを出力します。

例

コードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
void zeroesIndexes(int arr[], int maxZeroes, int n) {
   int start = 0, end = 0;
   int zeroesCount = 0;
   int bestWindowCount = 0, bestWindowStartIndex = 0;
   while (end < n) {
      if (zeroesCount <= maxZeroes) {
         if (arr[end] == 0) {
            zeroesCount++;
         }
         end++;
      }
      if (zeroesCount > maxZeroes) {
         if (arr[start] == 0) {
            zeroesCount--;
         }
         start++;
      }
      if ((end - start > bestWindowCount) && (zeroesCount <= maxZeroes)) {
         bestWindowCount = end - start;
         bestWindowStartIndex = start;
      }
   }
   cout << "The indexes are ";
   for (int i = 0; i < bestWindowCount; ++i) {
      if(arr[bestWindowStartIndex + i] == 0)
         cout << bestWindowStartIndex + i << " ";
   }
}
int main() {
   int arr[] = {1, 0, 0, 1, 1, 0, 1, 0, 1, 1};
   int maxZeroes= 2;
   zeroesIndexes(arr, maxZeroes, 10);
   return 0;
}

出力

上記のコードを実行すると、次の結果が得られます。

The indexes are 5 7

結論

チュートリアルに質問がある場合は、コメントセクションにそのことを記載してください。