問題タブ [subsequence]

N 個の異なる整数を含む配列が与えられた場合、次を満たす最長のサブシーケンスを見つけます。

1. サブシーケンスの開始要素は、サブシーケンスの最小です。
2. サブシーケンスの最後の要素は、サブシーケンスの最大のものです。

例: 8,1,9,4,7。答えは 1,4,7 です。

2,6,5,4,9,8. 答えは 2,6,5,4,9 または 2,6,5,4,8 です。

O(N^2)アルゴリズムは次のとおりです。

• を数値Xの配列とします。
• を繰り返しXます。index にいるとしますi。Y[j] がX [j] より小さいY要素の数である配列とします。(j, i]X [i] より小さいz要素の数を とします。[j, i]X[j] が X[i] より小さい場合、制約を満たす長さ zY[j] のサブシーケンスを取得できます。

• に設定zし1ます。下から までjループします。i-10

  if X[j] < X[i]: z++; ans = max(ans, z - Y[j]); else Y[j]++;

もっとうまくやれるでしょうか？O(NlogN)最大長を見つけるアルゴリズムが必要だと思います。

以下の形式でバッチ番号 (主キー) を生成する必要があるシナリオがあります。

バッチ番号: ( XX ) ( XXXXX ) 場所の順序

シーケンスは、バッチごとに 00001 から始まります。ただし、これを行うためのシーケンス番号ジェネレーターを使用することはできません。私の頭の上にある可能な解決策は次のとおりです。

1. 数値を保持する追加のテーブルを作成します。ただし、コミットされていないトランザクションが存在する可能性があるため、複数のユーザーが同じシーケンスを取得する可能性があります。
2. エンティティが保存されるたびに、その列から max(substring(batchnum,2)) を取得し、+1 を追加します。しかし、これはパフォーマンスに非常に大きな過負荷をもたらし、複数のユーザーが同じシーケンスを取得するという問題もあります。

文字列の可能なすべてのサブシーケンスを見つけようとしています。たとえば、この文字列の「abc」では、合計 8 個の文字列 2^3=8 の組み合わせが見つかります。a、b、c、ab、ac、bc、abc '\0' のように。しかし、私のコードは文字列のすべての文字のみを出力しています。どうやってやるの？

これは私の問題です：

がアイテム間の距離を超えない制約 (は –匿名変数のリスト として実装されて いる) のサブリストでdistance(List, Nemptylist, SubList)/3あるかどうかをチェックするプロシージャを作成します。 が完全にインスタンス化されていると仮定します。数が有限である限り、重複した回答が許可されます。SublistListNNNemptylistNList

たとえば、N= 2 の場合:

この問題を解決しようと何時間も座っていて、最終的に上記の例が機能しましたが、いくつかのテストを実行して失敗しました。

今のところ私の解決策は次のとおりです。

このテストを実行しようとすると:

ランタイム超過エラーが原因で失敗します。

何時間もデバッグしましたが、本当に疲れました。この恐ろしい任務を終わらせるのを手伝ってください。

以下は、再帰を使用して最大部分列の問題を解決するために記述された C++ のサンプル コードです。正確には部分列ではなく、最大部分列の合計です。

左の単一要素が負の場合、基本ケースが 0 を返さなければならないのはなぜですか? 実際の負の値ではなく、より高い値 0 を返した場合、合計に影響はありませんか? ベースケースの説明と問題文をインターネットで検索しましたが、説明を見つけることができませんでした。

subSequence が読み取り専用の charSequence を返すことはわかっています。また、String クラスは CharSequence を実装しています。subString は文字列を返します。

ただし、サブシーケンスとサブストリングの中で、いつ、どちらを優先するか

リートコードの問題があります: 別個のサブシーケンスです。

文字列 S と文字列 T が与えられたとき、S 内の T の別個の部分列の数を数えます。残りの文字の相対位置。(つまり、「ACE」は「ABCDE」のサブシーケンスですが、「AEC」はそうではありません)。

以下に例を示します: S = "うさぎ"、T = "うさぎ" 3 を返します。

私の質問:

ここで、 「S 内の T の異なるサブシーケンスの数を数える」の意味がわかりません 。「r」、「ra」、「b」rab」、「rabt」などはすべて T のサブシーケンスだと思います。 、そしてそれらも S にある. しかし、リターンは答え "3" を返す. だから、私は問題を誤解したにちがいありません. 誰か私にそれを説明できますか?どうやって解決するか、練習としてやってみたいと思います。

Online Encyclopedia of Integer Sequences は、クエリをサブシーケンスとして含むシーケンスの検索をサポートしています。を検索するsubseq:212,364,420,428と、シーケンスが返され8*n+4ます。( http://oeis.org/search?q=subseq:212,364,420,428 )

この驚くべき機能は、Russ Cox によってhttp://oeis.org/wiki/User:Russ_Cox/OEIS_Server_Featuresとして実装されたようですが、これがどのアルゴリズムで実装されているかは指定されていません。

どうやって作っているのか気になります。1 回の検索で 100 万近くのシーケンスを処理することは、検索エンジンにとって明らかに非現実的です。最初の数字のインデックス (Russ Cox が Google Code Regex Search を行ったのと同じ方法) を保持するだけでは、数字のようなもの0はほとんどすべてのシーケンスにあるため、残りをブルート フォースしても機能しません。実際、一部のクエリ0 1はデータベース全体の高いパーセンテージと一致するため、アルゴリズムは目的の出力サイズに敏感な実行時間を必要とします。

この機能がどのように実装されているか知っている人はいますか?

主な DNA シーケンス (文字列) が与えられ (文字列 1 とします)、検索する別の文字列 (文字列 2 とします) が与えられます。string2 がサブシーケンスである string1 で最小長のウィンドウを見つける必要があります。
string1 = "abcdefababaef"
string2 = "abf"

私が考えたが、機能していないように見えるアプローチ:
1. 最長共通サブシーケンス (LCS) アプローチを使用し、(LCS の長さ = string2 の長さ) かどうかを確認します。しかし、これにより、string2 がサブシーケンスとして string1 に存在するかどうかがわかりますが、最小のウィンドウではありません。
2. KMP アルゴリズムですが、変更方法がわかりません。
3. string2 にある string1 の {characters: pos of characters} のマップを準備します。次のように: { a : 0,6,8,10
b : 1,7,9
f : 5,12 }
そして、最小ウィンドウを見つけて「abf」の順序を維持するためのいくつかのアプローチ

自分が正しい方向に考えているのか、それとも完全に間違っているのか、よくわかりません。
これには既知のアルゴリズムがありますか、または誰かがアプローチを知っていますか? よろしくお願いします。
前もって感謝します。