1

次のケースがあり、重いループやスライスを行わずに一般的な解決策を得たいと考えています。

まず：

Nそれを介してリストサイズ（初期サイズ）を計算する初期化します：

この方程式を通してN(N-1)/2..

N = 5初期サイズが になるように設定したとしましょう10。

その後、リストに 1 と 0 をいくつかのメソッドで埋めます。

このような ：

0 1 0 1 1 1 0 1 0 1

このリストは、セグメントが (N-1) である N に従ってセグメント化されています。

そう

  • 最初のセグメントは次のとおりです。0 1 0 1
  • 2 番目のセグメントは次のとおりです。1 1 0
  • 3 番目のセグメントは次のとおりです。1 0
  • 第 4 セグメントは次のとおりです。1

[0 1 0 1] [1 1 0] [1 0] [1]

私がやりたいことは、入力 N として任意の数値を再度入力する場合です。

適切なシフトで以前のデータを維持する

新しいサイズによると、たとえば N=6 の場合、サイズは 15 になります。

したがって、4 つの代わりに 5 つのセグメントを使用します。

私はこのようにしたい：

[0 1 0 1 0 ] [1 1 0 0 ] [1 0 0 ] [1 0 ] [ 0 ]

逆に、最初に N = 7 を入力して入力すると、N = 4 と入力します。

正しい変速をしたい

4

5 に答える 5

2

それLinkedListがあなたにとって最も適切なコレクション クラスのようです。リスト内のどこからでも要素を一定時間内に挿入および削除できます。

以下に、N を 1 ずつ増減するアルゴリズムを示します。どちらの操作も O(N) です。

// the whole list of integers
var data = new LinkedList<int>();

// stores the final node of each segment
var segmentEnds = new LinkedList<LinkedListNode<int>>();

/* INCREASING */
// increase all existing segments by one
var node = segmentEnds.First;
while (node != null)
{
    node.Value = data.AddAfter(node.Value, 0);
    node = node.Next;
}

// add the last segment of size 1
segmentEnds.AddLast(data.AddLast(0));

/* DECREASING */
if (data.Count > 0)
{
    // remove the last element from each segment
    node = segmentEnds.First;
    while (node != null)
    {
        var temp = node.Value.Previous;
        data.Remove(node.Value);
        node.Value = temp;
        node = node.Next;
    }

    // remove the last (now empty) segment
    segmentEnds.RemoveLast();
}
于 2012-11-08T12:28:18.850 に答える
2

これらを単一のリストに入れなければならない理由はありますか? あなたが持っているのはここにn個のリストのリストがあるようですので、サイズ1からNまでのサイズのリストを保持するサイズNのリストを1つ作成します。このように、N を増やした場合、各リストに適切な数の 0 を追加し、0 だけで新しいリストを作成します。N を減らした場合、ルールが何であるかはわかりませんが、比較して削除するだけだと思います適切な数の短いリストを作成してから、他のリストから最後の要素を削除しますが、多くの要素を削除します。

単一の配列リストを持つという点では機能しませんが、説明したデータを保存するためのより良い方法だと思います。とにかく、私が説明したモデルからフラット化されたリストにいつでも簡単にアクセスできます...

于 2012-11-08T12:33:56.473 に答える
2

たぶん、二次元で考え始めて、 aが a であるのList<Segment>に対して aを使用する必要があります。これを使用すると、セグメントを簡単に追加/削除したり、すべてのセグメントを好きなように変更したりできるはずです。しかし、これは何らかの形で重いループにつながりますが、どのレベルでもループせずにこれを解決できないとは思いません。SegmentList<bool>

于 2012-11-08T12:35:04.807 に答える
1

基本的に、1 次元のリストを使用して 2D データ構造をモデル化しています。これは多少異例ですが、メモリを節約するために一般的に行われています。

最も簡単な解決策は、リストを拡張または縮小する際にコピーを作成することです。リストを短縮または拡張する必要がある場合は、ターゲット サイズの新しいリストを作成し、元のリストが 2D データ構造であるかのように、2 つのネストされたループを使用してコピーを行います。row、column、およびを取りN、ペアに対応する単純なリストにインデックスを返すマッピング関数を作成すると、{row, column}非常に役立つ場合があります。

private static int MakeIndex(int r, int c, int N) {
    return (N*(N+1)-(N-r)*(N+1-r))/2+c;
}

{r, c}size のリスト内のペアN1のインデックスを size のリスト内の同じペアのインデックスに変換できるようになりましたN2。

その場で拡大および縮小することで、このソリューションを改善できます。重要な問題は、あなたが行く方向です。縮小するときは、前から後ろに行きます。展開するときは、後ろから前に移動します。

于 2012-11-08T12:46:05.393 に答える
1 
int N = 5;
var array = Enumerable.Range(1, N - 1).Select(i => Fill(i))
                      .SelectMany(x => x)
                      .ToArray();

int[] Fill(int len)
{
    int[] arr = new int[len];
    for (int i = 0; i < len; i++) arr[i] = 1; //Fill
    return arr;
}
于 2012-11-08T12:32:52.497 に答える