C++ プログラム: 左右の回転が同じで最も長い数値の部分列を検索します。

この問題では、左右の回転が同じ場合のサブシーケンスの最大長を見つける必要があります。左回転とは、文字列内のすべての文字を左に移動し、最初の文字を末尾に移動することを意味します。右回転とは、すべての文字列文字を右に移動し、最後の文字を先頭に移動することを意味します。

問題ステートメント – 数値を含む文字列 str が与えられ、同じ左右の回転で最大長のサブシーケンスを見つける必要があります。

-str="323232",

– 6

- 左右の回転が同じ場合の最長のサブシーケンスは「323232」です。左に回転すると「232323」、右に回転すると「232323」になります。

-str = '00010100'

– 6

– 同じ左右の回転を持つ最長のサブシーケンスは「000000」です。

-str = '092312110431010'

– 6

– 同じ左右の回転を持つ長さ 6 のサブシーケンスが 2 つ考えられます。 1 つ目は「010101」、2 つ目は「101010」です。 方法1

このメソッドでは、指定された文字列の考えられるすべてのサブシーケンスを検索します。次に、文字列の左右の回転が同じかどうかを確認します。再帰的方法を使用して、考えられるすべてのサブシーケンスを見つけます。

「maxLen」グローバル変数をゼロに初期化し、左回転と右回転で同じ最長のサブシーケンスの長さを格納します。

• isRightSameLeft() 関数を定義して、文字列の左回転と右回転が同じかどうかを確認します。

• 関数内で、substr() メソッドを使用して文字列を左右に回転します。

• getAllSubSeq() 関数は、指定された文字列の考えられるすべてのサブシーケンスを検索するために使用されます。

• 基本ケースを定義します。 str が空の場合、サブシーケンスを取得し、isRightSameLeft() 関数を実行して、サブシーケンスの左右の回転が同じかどうかを確認します。その場合、「maxLen」変数の長さが「maxLen」の現在の値より大きい場合は、その値を更新します。

• 「str」から最初の文字を削除し、「out」文字列を追加した後、再帰呼び出しを行います。

• 最初の文字を削除し、「out」文字列を変更しないままにした後、別の再帰関数呼び出しを実行します。この再帰呼び出しでは、「str」の最初の文字を除外します。

• ＃＃＃例＃＃＃ リーリー ＃＃＃出力＃＃＃ リーリー

  時間計算量 - O(N*2N)。ここで、左右の回転を比較するには O(N)、考えられるすべてのサブシーケンスを見つけるには O(2N) を使用します。

スペースの複雑さ - 余分なスペースを使用しないため、O(1)。

方法 2

ここでは、上記の方法を最適化しました。サンプル入力の解を観察できます。サブシーケンスの左回転と右回転が同じになるのは、サブシーケンスに同じ文字が含まれるか、2 つの異なる文字が交互に含まれ、長さが偶数である場合のみです。

2 つのネストされたループを使用して、任意の 2 つの数値を結合します。

'cnt' 変数を定義して、2 つの数値を交互に含む部分列の長さを見つけ、それをゼロに初期化します。

次の文字が i 番目の文字であるべきか j 番目の文字であるべきかを追跡するために、ブール型の「最初の」変数を定義します。
ループを使用して文字列を走査します。
first == true かつ str[k] - '0' == I の場合、'first' の値を交互に変更し、'cnt' を 1 ずつ増分します。
first == false かつ str[k] - '0' == j の場合、'first' の値を再度交互に変更し、'cnt' を 1 ずつ増分します。
i と j が等しくなく、「cnt」の値が奇数の場合は、1 ずつ減分します。
cnt 値が "res" より大きい場合は、"res" 変数の値を更新します。

• ＃＃＃例＃＃＃ リーリー ＃＃＃出力＃＃＃ リーリー
時間計算量 - O(10*10*N)。数値の組み合わせを含む文字列から部分列を見つけるためです。

• 空間の複雑さ - O(1)。動的空間を使用しないためです。

このチュートリアルでは、同じ左右の回転を含む最長のサブシーケンスを見つける 2 つの方法を説明します。最初の方法は単純な方法です。この方法は非常に時間がかかり、大量の入力には使用できません。

• 2 番目の方法は最適化されており、その時間計算量は O(N) にほぼ等しいです。

以上がC++ プログラム: 左右の回転が同じで最も長い数値の部分列を検索します。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。