隣接しない文字を削除してバイナリ文字列を降順に並べ替えられるかどうかを確認します

この問題では、隣接しない要素のみを削除して、指定されたバイナリ文字列を降順に並べ替える必要があります。

この問題を解決するには、バイナリ文字列内の 1 の前にある 0 をすべて削除する必要があります。文字列のどこかに 2 つの連続する 0 とそれに続く 2 つの連続する 1 が見つかった場合、文字列を降順に並べ替えることができないことを意味します。それ以外の場合は、それぞれの状況を分類できます。

問題文 - 長さが N に等しいバイナリ文字列 str が与えられています。文字列から複数の隣接しない文字を削除することで、指定された文字列を降順に並べ替えられるかどうかを確認する必要があります。指定された文字列。文字列を降順にソートできる場合は「yes」を出力し、そうでない場合は「no」を出力します。

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

イラスト

2 番目と 4 番目の位置から「0」を削除すると、文字列を降順に並べ替えることができます。

リーリー リーリー

イラスト

文字列がソートされました。

リーリー リーリー

イラスト

ここでは、文字列を並べ替えるために 1 番目、3 番目、4 番目、5 番目の位置にある 0 を削除する必要がありますが、隣接する 0 を削除することはできません。あるいは、すべての「1」を削除して文字列をソートすることもできますが、これも 2 つの「1」が隣接しているため不可能です。

方法1

このメソッドでは、文字列を末尾から繰り返し処理します。 2 つの連続した「1」が見つかった場合、ループは終了します。その後、文字列に 2 つの連続した「0」が含まれているかどうかを確認します。その場合は false を返します。それ以外の場合は true を返します。

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

ステップ 1

- for ループの使用を開始して、文字列を 'len – 2' から 0 まで反復処理します。ここで、「len」は指定されたバイナリ文字列の長さです。

• ステップ 2
- str[i] と str[i 1] の両方が「1」に等しい場合は、「break」キーワードを使用してループを終了します。

• ステップ 3
- 次に、i 番目のインデックスから文字列の走査を開始します。

• ステップ 4
- str[j] と str[j 1] が両方とも '0' に等しい場合は、0 を返します。ループが正常に終了すると 1 を返します。

• p>ステップ 5

- isSortPossible() 関数の戻り値に基づいて、ドライバー コードで「YES」または「NO」を出力します。

• ＃＃＃例＃＃＃ リーリー ＃＃＃出力＃＃＃ リーリー 時間計算量 - O(N)、文字列を反復処理する場合。

空間の複雑さ - O(1)

方法 2

このメソッドでは、最初のメソッドと同じロジックを使用しますが、コードを最適化して読みやすくしています。ここでは、2 つの別々のループを使用する代わりに、1 つのループのみを使用して、2 つの連続する「0」の後の 2 つの連続する「1」を検出します。

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

ステップ 1

- 「isTwoZeros」変数を定義し、「false」値で初期化します。

ステップ 2

- 文字列のインデックス 0 から「len - 1」までの反復を開始します。

• ステップ 3
- str[i] と str[I 1] が「0」で、「isTwoZeros」が false の場合、「isTwoZeros」の値を true に変更します。これは、指定された文字列に 2 つの連続するゼロが含まれていることを意味します。

• ステップ 4
- else 部分で、str[i] と str[I 1] が '1' で、'isTwoZeros' が true に等しい場合、関数から。これは、2 つの連続する 0 の後に 2 つの連続する「1」が得られることを意味します。

• ステップ 5
- for ループのすべての反復が終了すると true を返します。

• ＃＃＃例＃＃＃ リーリー ＃＃＃出力＃＃＃ リーリー 時間計算量 - O(N)

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

  隣接しない文字のみを削除してバイナリ文字列を降順に並べ替える 2 つの方法を学習しました。どちらの方法でも、コードへの変更を最小限に抑えながら同じロジックを使用します。 2 番目のアプローチのコードは、最初のアプローチのコードよりも読みやすくなっています。

以上が隣接しない文字を削除してバイナリ文字列を降順に並べ替えられるかどうかを確認しますの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。