文字列配列から A 0 と B 1 で構成される最長のサブセットの長さを見つけます。

この問題では、最大でも A 0 と B1 を含む最長のサブセットを見つける必要があります。必要なのは、配列要素を使用して考えられるすべてのサブセットを見つけ、最大でも A 0 と B1 を含む最長のサブセットを見つけることだけです。

このチュートリアルでは、まず問題を解決するための再帰的手法を学習します。その後、動的プログラミング手法を使用してコードを最適化します。

問題文 - N 個のバイナリ文字列を含む配列が与えられています。さらに、A と B の整数が与えられます。指定されたバイナリ文字列を使用して、A 0 と B1 より多くが含まれないように最長のサブセットを作成する必要があります。

＃＃＃例＃＃＃ リーリー リーリー

イラスト

最長のサブセットは { "0", "0", "1"} で、2 つの 0 と 1 つの 1 が含まれます。

リーリー リーリー

イラスト

最長のサブセットは、{"0"、"101"、"0"、"1"}、3 つの 0 と 3 つの 1 です。

方法1

このセクションでは、再帰を使用した簡単な方法を学びます。配列要素を使用して考えられるすべてのサブセットを構築し、A 0 と B 1 を含む最長のサブセットを見つけます。

＃＃＃アルゴリズム＃＃＃

ステップ 1

- countZeros() 関数を定義して、指定されたバイナリ文字列内のゼロの合計数をカウントします。

• ステップ 1.1
- 「count」変数をゼロに初期化します。

• ステップ 1.2
- for ループを使用して文字列を反復処理します。

• ステップ 1.3
- i 番目のインデックスの文字が「0」の場合、「cnt」の値を 1 増やします。

• ステップ 1.2
- 「cnt」変数の値を返します。

• ステップ 2
- getMaxSubsetLen() は整数値を返し、ベクトル arr、int A、int B、およびインデックスを引数として受け取ります。

• ステップ 3
- 関数内の基本ケースを定義します。インデックスがベクトルのサイズと等しい場合、または A と B の値が両方とも 0 の場合は 0 を返します。

• ステップ 4
- 次に、インデックスの文字列内のゼロの合計数を数えます。

• ステップ 5
- 文字列の長さから 1 の合計数を減算して、1 の合計数を取得します。

• ステップ 6
- 「最初の」変数を 0 に初期化します。

• ステップ 7
- 0 と 1 の合計数がそれぞれ A と B より小さい場合、現在のバイナリ文字列が含まれます。再帰関数呼び出しの戻り値を 1 格納します。再帰呼び出しを行うと、A と B から 0 と 1 が減算されます。

• ステップ 8
- 現在の文字列を除外し、結果の値を「2 番目」の変数に保存します。

• ステップ 9
- 1 番目と 2 番目の最大値を返します。

• ＃＃＃例＃＃＃ リーリー ＃＃＃出力＃＃＃ リーリー 時間計算量 - N 個の配列要素を使用してすべての可能なサブセットを見つけるため、O(2N)。

空間の複雑さ - O(1)

方法 2

このセクションでは、上記の方法を最適化しました。この問題を解決するために、私たちは動的プログラミング手法を使用します。問題の時間の複雑さを軽減するために、前の状態の結果を保存します。

＃＃＃アルゴリズム＃＃＃

ステップ 1

- 上記のメソッドで行ったのと同じように、特定のバイナリ文字列内のゼロの総数をカウントする countZeros() 関数を定義します。

ステップ 2

- サイズ A x B x N の 3 次元ベクトルを作成して、前の状態の結果を保存します。リストでは、合計 0 が A に等しく、1 が B に等しい場合、インデックス "I" にサブセットの長さを格納します。さらに、それを引数として getMaxSubsetLen() 関数に渡します。

• ステップ 3
- 上記の方法で行ったように、基本ケースを定義します。

• ステップ 4 - dpTable[A][B][index] の値が 0 より大きい場合、ステータスが計算され、その値が返されたことを意味します。

• ステップ 5
- 現在の文字列内の 0 と 1 の合計数を数えます。

• ステップ 6
- 現在の文字列を含むおよび除外した結果の値を取得します。

• ステップ 7
- max() 関数を使用して最初と 2 番目の最大値を取得し、それを dpTable[A][B][index] に保存した後、return

• ＃＃＃例＃＃＃ リーリー ＃＃＃出力＃＃＃ リーリー 時間計算量 - O(A*B*N)、結果を取得するには 3D リストにデータを入力する必要があるため。

動的プログラミング手法に 3D リストを使用するため、空間複雑度 - O(A*B*N)。

以上が文字列配列から A 0 と B 1 で構成される最長のサブセットの長さを見つけます。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。