問題タブ [lis]

私には習慣がありますAbstractTableModel

そのモデルはデータをHashMap. だから私の方法のためにgetValueAt(int rowIndex, int columnIndex)

そうです

ただし、私のデータには 2000 を超えるエントリがあるため、テーブルのデータを取得する必要があるたびにこれを行うと、パフォーマンスが大幅に低下します。

では、どのようなソリューションをお勧めできますか?

Listすべてのデータを の代わりに に保存するためにを使用する必要がありHashMapますか?
テーブル モデルを使用する場合にデータを格納するために受け入れられている標準は何ですか?

提案してくれた人に感謝します。愚かな質問かもしれないことをお詫びしますが、テーブルとテーブルにデータを保存する方法に関してはあまり得意ではありません。

私はうまく機能する次のアルゴリズムを持っています

ここで自分で説明しようとしましたhttp://nemo.la/?p=943そしてここで説明されています http://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/同様に、スタックオーバーフローでも

最長の非単調増加サブシーケンスを生成するように変更したい

シーケンス 30 20 20 10 10 10 10 の場合

答えは 4 である必要があります: "10 10 10 10"

しかし、nlgn バージョンのアルゴリズムでは機能しません。最初の要素「30」を含むように s を初期化し、2 番目の要素 = 20 から開始します。次のようになります。

1. 最初のステップ: 30 は 20 以下です。20 より大きい最小の要素を見つけます。新しい s は「20」になります。

2. 2 番目のステップ: 20 は 20 以上です。シーケンスを拡張すると、s には "20 20" が含まれます。

3. 3 番目のステップ: 10 は 20 以下です。「20」である 10 より大きい最小の要素を見つけます。新しい s は「10 20」になります

その後、s は決して大きくならず、アルゴリズムは 4 ではなく 2 を返します。

再帰を使用して、可能なすべての最長増加サブシーケンスを見つけようとしました。入力配列を試したところ、{10,22,9,33,21,50,41,40,60,55}うまくいき、出力は次のようになりました。

しかし、入力配列を試した{2,-3,4,90,-2,-1,-10,-9,-8}ところ、次の出力が得られました。

この場合、取得できませんでし2 4 90た。この場合の言葉にするために、コードの何を変更する必要がありますか?

長さ n (以下の例では n = 6) のポイントのリストがあります。その後、これらのデフォルト ポイントに基づいて他のポイントをいくつか作成しました。私が持っているデータ構造に基づいていますが、式のチェーンを取得するにはどうすればよいですか? たとえば、ポイント 10 (再帰的または非再帰的) の場合、このポイントがどこから来ているかをどのように言えますか?.

ポイント10がどのように作られているか知りたい場合は、次のようなものを返さなければなりません:

私はアルゴリズムを練習しており、私のタスクの 1 つは、指定された0 < n <= 10^6の数値について、すべての最長増加サブシーケンスの数を数えることです。ソリューションO(n^2)はオプションではありません。

LIS とその長さ ( LIS Algorithm ) を見つけることは既に実装していますが、このアルゴリズムは数値を可能な限り低い値に切り替えます。したがって、前の数 (大きい方) を持つサブシーケンスが最長の長さを達成できるかどうかを判断することは不可能です。

O(nlogn)についてこれを取得する方法はありますか? 動的計画法を使用して解決する必要があることを私は知っています。

私は1つのソリューションを実装し、うまく機能しますが、2つのネストされたループ(i in 1..n) x (j in 1..i-1)が必要です。O(n^2)
だと思いますが、遅すぎます。

これらの数値を配列から二分木に移動しようとさえしました (各i反復で、 number[i]よりも小さいすべての数値を探すため- 要素i-1..1を通過するため)、さらに遅くなりました。

テスト例:

EDIT
最後に、この「ブルートフォース」メソッドが正しくないことがわかりました。
そこで、LIS 問題を解決する別の 2 つの方法を書きます。

• 元の配列と並べ替えられた配列で LCS を使用します。時間計算量 = (n^2)。
• DP + 二分探索を使用します。時間計算量 = O(nlgn)。

【コードは最後にあります。】

---

総当たりを使用して、最長増加部分列 (LIS) を見つけようとしています。しかし、個人的には、このアルゴリズムの時間計算量は O(n ² ) で、DP アプローチと同じだと思いますが、正しいですか?

---

[編集]
[LCS法]

【DP＋二分探索法】

私は最近、hyper-v で真新しい gen 2 仮想マシンを作成し、最近リリースされた ubuntu 14.04 バージョンをインストールしました。

apt-get update の後でも、起動時に、Windows Server 2012 R2 Hyper-V サーバーは、hyper-v イベントログのダウンレベル ドライバーについて不平を言います

合成ディスプレイ ドライバー: 'Dev Ubuntu 14.04 Gen2' のデバイス 'Microsoft 合成ディスプレイ コントローラー' が読み込まれていますが、サーバーとはバージョンが異なります。サーバー バージョン 3.3 クライアント バージョン 3.2 (仮想マシン ID 9FC171E7-B2C6-4BD2-9FF0-253209B2A69D)。デバイスは動作しますが、これはサポートされていない構成です。これは、この問題が解決されるまでテクニカル サポートが提供されないことを意味します。この問題を解決するには、統合サービスをアップグレードします。アップグレードするには、仮想マシンに接続し、[アクション] メニューから [統合サービス セットアップ ディスクの挿入] を選択します。（もちろん、これはうまくいかないようです）

と

データ交換統合サービス: Hyper-V Data Exchange は仮想マシン 'Dev Ubuntu 14.04 Gen2' に接続されていますが、バージョンが Hyper-V で期待されるバージョンと一致しません (仮想マシン ID 9FC171E7-B2C6-4BD2-9FF0-253209B2A69D)。フレームワークのバージョン: 交渉済み (3.0) - 期待 (3.0); メッセージのバージョン: 交渉済み (4.0) - 予想 (5.0)。これはサポートされていない構成です。これは、この問題が解決されるまでテクニカル サポートが提供されないことを意味します。この問題を解決するには、統合サービスをアップグレードします。アップグレードするには、仮想マシンに接続し、[アクション] メニューから [統合サービス セットアップ ディスクの挿入] を選択します (同様に、これは機能していないようです)。

また、hyper-v は、Windows 2012 R2 hyper-V Manager の [概要] タブにある "統合サービス: 更新が必要です" について不平を言います。

私の (明らかに間違った) 信念は、Linux Integration Services がカーネルに統合されているため、Trusty は 2012 R2 hyper-v サービスと互換性があるというものでした。

私のubuntu仮想マシンがhyper-v 2012 r2を使用して完全にサポートされるように、14.04用の更新された統合サービスパッケージをどこで/どのように入手するか、および正しいインストール手順を誰かが説明できますか?

助けてくれてどうもありがとう、ダグ・コールマン

スタックを使用して、配列を反復しながら増加するサブシーケンスを記録し続けることができます。各要素はスタックに 1 回出入りするため、実行時間は線形です。

その長さではなく実際のシーケンスを出力したい場合は、開始インデックスを記録し、その後のすべての要素をより大きな値で見つけることができます。

この線形時間アルゴリズムは機能しますか?