C++ プログラム: 左右の回転が同じで最も長い数値の部分列を検索します。
- PHPz転載
- 2023-08-30 13:33:11717ブラウズ
この問題では、左右の回転が同じ場合のサブシーケンスの最大長を見つける必要があります。左回転とは、文字列内のすべての文字を左に移動し、最初の文字を末尾に移動することを意味します。右回転とは、すべての文字列文字を右に移動し、最後の文字を先頭に移動することを意味します。
問題ステートメント – 数値を含む文字列 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 番目の文字であるべきかを追跡するために、ブール型の「最初の」変数を定義します。
-
＃＃＃例＃＃＃ リーリー ＃＃＃出力＃＃＃ リーリー 時間計算量 - O(10*10*N)。数値の組み合わせを含む文字列から部分列を見つけるためです。 -
空間の複雑さ - O(1)。動的空間を使用しないためです。
このチュートリアルでは、同じ左右の回転を含む最長のサブシーケンスを見つける 2 つの方法を説明します。最初の方法は単純な方法です。この方法は非常に時間がかかり、大量の入力には使用できません。 -
2 番目の方法は最適化されており、その時間計算量は O(N) にほぼ等しいです。
以上がC++ プログラム: 左右の回転が同じで最も長い数値の部分列を検索します。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。