問題タブ [subsequence]

私は動的プログラミングの基礎を学んでいて、配列内の最長増加部分列を見つけるという問題に行き着きました。DP ソリューションを調べる前に、自分でコーディングすることにし、次のアルゴリズムを思いつきました。完全なコードは、こちら にあります。

アイデアは、リスト配列を作成して増加するすべてのサブシーケンスを格納し、各サブシーケンスの対​​応する最大値を格納して比較を高速化することです。

コードは O(n^2) 時間で実行され、小規模/中規模の入力に対して完全に機能します。ただし、一部のオンライン プラクティス ポータル ( HackerRankなど) に対してコードを実行しようとすると、TLE (Time Limit Exceeded Errors) と Wrong Answer の両方が表示されます。効率的なソリューションは DP O(nlogn) ソリューションであるため、TLE エラーは理解していますが、このアルゴリズムによって生成される間違った回答について混乱しています。このような場合の入力は大きすぎる (~10000) ため、解決策がどこでうまくいかないかを手動で確認することはできません。

完全なコードとデータ セットの 1 つへの出力は、ここにあります。正解は、HackerRank によって報告された 195 である必要があります。

私はこれら2つの問題の違いは何かを考えようとしています

与えられた数列 S

1) S の最長回文部分列を見つけます。

2) 逆もまた S のサブシーケンスである S の最長のサブシーケンスを見つけます。2 つのサブシーケンスは同じである可能性があります。
元の言い回しは、S' と同じサブシーケンスと S' の逆のサブシーケンスが存在するように、S の最長サブシーケンス S' を見つけます。

2 つの問題に対して私が導き出した DP の定式化は同じです。

それらは実際に同じ問題ですか？私はこのように考えようとしてきました: 最長の回文サブシーケンスが であると仮定するとlongestP、それlongestP自体は明らかに 2) に対する可能な答えです。

2) に対するより長い答えはありますか? と呼ばれるものがあると仮定するとlongerP、 の逆longerPも S のサブシーケンスであり、それを と呼びますreverseLongerP。longerP重複してもしなくても、とからより長い回文を構築できますreverseLongerP。longestPしたがって、最長の回文であるという私たちの仮定と矛盾します。

2）に対するより短い答えはありますか？longestP2) はそのような種類の最長のサブシーケンスを見つけるように求めており、すでに可能な答えであるため、より短いサブシーケンスはlongestP考慮すべきではないため、そうは思いません。

上記はこの問題に対する私の考えですが、何か足りないものはありますか?

私の結論は、それらは同じ質問であるということです。しかし、回文ではない文字列 s とその逆を含むシーケンスを部分シーケンスとして与えるように求められましたが、このシーケンスには s より長い回文はありません。ありえないと思います。

私の考えでは、そのような数列が存在すると仮定すると、s とその逆は の長さの回文を形成できるlength_of_s + length_of_reverse_s - length_of_overlapので、この回文の最小の長さは になりますlength_of_s。しかし、その場合、length_of_overlapは に等しいlength_of_sので、 s とその逆は同じでなければならず、 s は回文でなければならず、これは s が回文であってはならない制限に違反します。

手元に複雑な問題があります。つまり、巨大な（200000文字以上）の問題があります:-

出力は次のようになります:-

ruby/c/c++ を使用して最長の繰り返し文字列を見つける方法はたくさんありますが、すべての繰り返し部分文字列を見つける方法はほとんどありません。

この操作を実行するための従来のアルゴリズムを探しています。フロイドのサイクル発見アルゴリズムがあるように。サイクルなどを識別するためのものです。そのようなものは、始めるのに最適です。

"abccdde" などの String の最長部分列を検索し、辞書 {"ab","add","aced"} を指定します。上記の例の結果は「追加」です

インタビューで聞かれたので、トライ木を使って答えました。最悪のケースは O(n*m) で、n は s の長さ、m は辞書の長さです。しかし、私の平均コストは非常に低いはずです。面接担当者が私の解決策が最善ではないと考えたため、面接に失敗しました。誰かがより良いアイデアを持っていますか?

Swiftでサブシーケンスを扱うとき、

func suffix(from: Int)just と同じようですdropFirst(_:)(明らかに、長さ「10」の配列の場合、入力値を「3」から「7」に変更するだけです。)

それを繰り返すだけです。したがって、もちろん、たとえば長さ 10 の配列の場合です。つまりfunc suffix(from: Int)dropFirst(_:)、たとえば"2" は"8" と同じです。

同様にupTo/throughと同一のようですdropLast(_:)

利便性以外に違いはありますか？

(おそらく、エラー状態、パフォーマンス、または?)

実際、Swift の内部で、どちらか一方が他方を呼び出すことによって実装されているだけなのか疑問に思っていました。

データフレームのリストでデータフレームを分割したいと思います。それを分割する理由は、常にfatherが続きmother、次に が続くということoffspringです。ただし、これらのファミリ メンバーには複数の行がある場合があります (これらは常に連続しています。たとえばfather、番号 1 は行 1 と行 2 にあります)。以下の例では、2 つのファミリがあり、2 つのデータ フレームを含むリストを取得しようとしています。

私の入力：

したがって、期待される出力dfout[[1]]は次のようになります。

値のシーケンス [1,2,3,4,1,5,1,6,7] があり、長さが増加する最長のサブシーケンスを見つける必要があります。ただし、関数は、前の数値よりも低い数値に達したらカウントを停止する必要があります。その場合のこのシーケンスの答えは [1,2,3,4] です。リセットされる前に4つの値があるため。このための Python コードをどのように記述すればよいでしょうか?

注：「最長の増加する部分列」を見つけることは一般的な課題のようです。そのため、オンラインで検索すると、列全体の長さを数え、減少を無視して増加する値の部分列を返す多くの解決策が見つかります。この場合、[1,2,3,4,5,6,7] が返されます。それは私が探しているものではありません。

各サブシーケンスをカウントし、前の数よりも小さい数に達したらカウントをリセットする必要があります。次に、カウントされたすべてのサブシーケンスを比較し、最も長いものを返す必要があります。

前もって感謝します。