バイナリ文字列内の最長の非増加サブシーケンス

この問題では、指定された文字列の最長の非増加サブシーケンスを見つける必要があります。

非増加とは、文字が同じか降順であることを意味します。バイナリ文字列には「0」と「1」のみが含まれるため、結果の文字列は「1」で始まり「0」で終わるか、「0」または「1」で始まり「1」で終わる必要があります。

この問題を解決するには、文字列の各位置で接頭辞「1」と接尾辞「0」を数え、接頭辞「1」と接尾辞「0」の最大合計を求めます。

問題文 - バイナリ文字列 str が与えられています。指定された文字列から最長の非増加サブシーケンスを見つける必要があります。

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

イラスト

最長の非増加サブシーケンスは「1100」です。

リーリー リーリー

イラスト

最長の非増加サブシーケンスは「111000」です。

リーリー リーリー

イラスト

最長の非増加サブシーケンスは '00000000' で、これは指定された文字列と同じです。

方法1

このメソッドでは、インデックスごとにプレフィックス「1」とサフィックス「0」の数を配列に保存します。その後、両方の配列の同じインデックスから値を取得し、それらを加算して、最大合計を見つけます。

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

ステップ 1

- pre1s 配列と suffix0s 配列を定義して、プレフィックス 1 とサフィックス 0 を保存します。さらに、すべての配列要素を 0 に初期化します。

• ステップ 2
- for ループを使用して文字列を反復処理し、各インデックスのプレフィックス 1 を計算します。 i > 0 の場合、前の要素の値が現在の要素に追加されます。

• ステップ 3
- 現在の文字が「1」の場合、pre1s[i] の現在の値に 1 を加算します。

• ステップ 4
- 次に、指定された文字列内のサフィックス 0 を数えます。文字列を末尾からトラバースします。

• ステップ 5
- 「I」の値が「n – 1」に等しくない場合は、「I 1」要素の値を取得し、それを現在の要素に追加します。

• ステップ 6
- 現在の要素が「0」の場合、現在の要素に 1 を加算します。

• ステップ 7
- ここで、「res」変数を 0 で初期化します。

• ステップ 8
- ループを使用して「pre1s」と「suffix0s」を繰り返します。

• ステップ 9
- 「pre1s」配列と「suffix0s」配列の i 番目のインデックスから値を取得し、それらを加算します。さらに、「sum」が「res」変数の現在の値より大きい場合、「res」変数の値は「sum」の値で変更されます。

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

• ＃＃＃例＃＃＃ 入力 '010100' の場合、プレフィックス配列は [0, 1, 1, 2, 2, 2]、サフィックス 0 配列は [4, 3, 3, 2, 2, 1] です。合計配列は [4, 4, 4, 4, 4, 1] となり、合計配列の最大値は 4 になります。したがって、答えは4となります。

  リーリー ＃＃＃出力＃＃＃ リーリー
時間計算量 - O(N)、プレフィックス 1 とサフィックス 0 で配列を初期化する必要があるため。

空間複雑度 - プレフィックス 1 とサフィックス 0 を配列に格納するため、O(N)

方法 2

この方法では、まずゼロの合計数を数えます。その後、文字列の反復処理を開始し、「1」を数え続け、0 が見つかった場合は「0」ずつ減分します。さらに、各反復で 0 と 1 のカウントを加算し、結果の最大値を見つけます。

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

ステップ 1

- 「count1」、「count0」、および「res」変数を定義し、0 で初期化して、カウント 1、0、および最終結果をそれぞれ保存します。

ステップ 2

- 文字列をループして「count0」変数に保存することで、ゼロの合計数をカウントします。

• ステップ 3
- 次に、ループを使用して文字列を反復処理します。

• ステップ 4
- ループ内で、現在の文字が「1」の場合は、「count1」の値を 1 ずつ増やします。それ以外の場合は、「count0」の値を 1 ずつ減らします。

• ステップ 5
- さらに、「res」と「count0 count1」の最大値を「res」変数に格納します。

• ステップ 6
- ループが終了したら、「res」変数の値を返します。

• ＃＃＃例＃＃＃ リーリー ＃＃＃出力＃＃＃ リーリー 時間計算量 - O(N)。文字列内のゼロの合計数を数え、文字列を走査して最長の部分列を見つけるためです。

空間の複雑さ - O(1)
• ＃＃＃結論は＃＃＃

  ここでは、両方の方法の時間計算量は同じですが、空間計算量が異なります。 2 番目の方法ではコードを最適化するときに定数スペースを使用しますが、最初の方法では動的スペースを使用してプレフィックス 1 とサフィックス 0 の合計数を保存します。

以上がバイナリ文字列内の最長の非増加サブシーケンスの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。