2 つの 1 の間に少なくとも K 個の 0 が存在するように、指定されたバイナリ配列で反転する 0 の数を最大化します。

バイナリ配列は、数値 0 と 1 のみを含む特別なタイプの配列です。この問題では、バイナリ配列と整数 K が与えられます。私たちのタスクは、2 つの 1 の間に少なくとも K 個の 0 が存在するように、指定されたバイナリ配列で 1 に反転できる 0 の最大数を計算することです。

例例

リーリー リーリー

説明

の中国語訳は次のとおりです:

説明

上記の配列の 3 番目と 6 番目のインデックスは唯一の有効なインデックスであり、2 つの 1 の間に少なくとも 2 つの 0 が存在するように反転することができます。したがって、結果の配列は {1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0}

となります。 リーリー リーリー

説明

の中国語訳は次のとおりです:

説明

上記の配列の 3 番目のインデックスが唯一の有効な反転インデックスです。

＃＃＃アプローチ＃＃＃

配列と整数 k を使用した上記の例を見てきました。メソッド −

に進みましょう。

この方法のアイデアは、2 つの 1 の間に連続する 0 の数を数え、それらの間のいくつかの 0 を 1 に反転することが適切かどうかを確認することです。 2 つの 1 の間に X 個のゼロがあると仮定します。観測によれば、反転できる 0 の数は (X-K) / (K 1) です。したがって、配列を反復処理して、1 の各ペアの間に連続する 0 が何個あるかを記録します。次に、反転できる 0 の数を変数 count に加算します。これが目的の応答になります。

次の方法について段階的に説明します -

最初に、指定された配列 'arr' と整数 'K' をパラメータとして受け取り、必要な整数 'count' を返す 'onesCount' という関数を作成します。
変数 count と lastIdx を作成します。
変数 count を 0 で初期化します。これは、fillip 0 の数を格納するために使用されます。
(-(K 1)) を使用して変数 lastIdx を初期化し、配列内の最後のインデックスを値 1 で保存します。
for ループを使用して配列を反復処理し、現在の要素が 1 であるかどうかを確認し、連続する 2 つの 1 の間に 1 を追加するのに十分な 0 があるかどうかを確認します。最後に、最後の 1 のインデックス値を更新します。
配列内の 0 の最後のセグメントを計算し、それを変数 count に追加する条件を記述します。
最後に、最終的な回答数が返されます。
Example

の中国語訳は次のとおりです:

Example

以下は、2 つの 1 の間に少なくとも k 個の 0 が存在することを保証するために、0 から 1 への最大変換を計算する C プログラムです。

リーリー ＃＃＃出力＃＃＃ リーリー

時間と空間の複雑さ

配列をトラバースするだけなので、上記のコードの時間計算量は O(N) です。ここで、N は指定された配列のサイズです。 余分なスペースを使用していないため、上記のコードのスペース複雑さは O(1) です。

＃＃＃結論は＃＃＃

このチュートリアルでは、2 つの 1 の間に少なくとも K 個の 0 が存在するように、指定されたバイナリ配列で反転する 0 の最大数を見つけるプログラムを実装しました。この問題は、2 つの 1 の間に連続する 0 の数を数え、それらの間のいくつかの 0 を反転することが適切かどうかを確認することで解決されます。時間計算量は O(N)、空間計算量は O(1) です。ここで、N は文字列のサイズです。

以上が2 つの 1 の間に少なくとも K 個の 0 が存在するように、指定されたバイナリ配列で反転する 0 の数を最大化します。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。