1

我有以下情况，我想获得一个没有大量循环和切片的通用解决方案。

首先 ：

我初始化N它通过它计算列表大小（初始大小）：

通过这个方程N(N-1)/2..

假设我设置N = 5了初始大小为10.

之后，我用一些方法用一个和零填充列表。

像这样 ：

0 1 0 1 1 1 0 1 0 1

该列表根据 N 分段，其中分段为 (N-1)。

所以

  • 第一段是：0 1 0 1
  • 第二段是：1 1 0
  • 第三部分是：1 0
  • 第四段是：1

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

我想做的是，如果我再次输入任何数字作为输入 N：

通过适当的移位保持以前的数据

根据新尺寸。例如，如果 N=6，则尺寸为 15

所以我将有 5 个段而不是 4 个

我想要这样：

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

反之亦然，如果我首先输入 N = 7 并填写它。然后我输入 N = 4

我想做正确的转变

4

5 回答 5

2

有什么理由必须将这些放在一个列表中？似乎您所拥有的是此处的 n 个列表的列表，因此创建一个大小为 N 的列表，其中包含大小为 1 到 N 的列表。这样，当您增加 N 时，您只需在每个列表中添加适当数量的 0 并创建只有 0 英寸的新列表。如果您减少 N，我不确定规则是什么，但我怀疑相比之下您只会删除短列表的适当数量，然后从其他列表中删除最后但许多元素。

就拥有一个数组列表而言，它不起作用，但它是存储您描述的数据的更好方法，我会说。无论如何，您总是可以很容易地从我描述的模型中获得扁平化列表......

于 2012-11-08T12:33:56.473 回答
2

也许您应该开始考虑二维并使用 aList<Segment>而 aSegment是 a List<bool>。通过使用它，您应该能够轻松地添加/删除段或以您喜欢的方式更改所有段。但这会以某种方式导致严重的循环，但我认为如果没有任何级别的循环，你就无法解决这个问题。

于 2012-11-08T12:35:04.807 回答
2

这似乎LinkedList是最适合您的集合类。它使您能够在列表中的任何位置以恒定的时间插入和删除元素。

下面给出了将 N 加一和减一的算法。两个操作都是 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 回答
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 回答
1

本质上，您正在对具有一维列表的 2D 数据结构进行建模。尽管它有些不正统，但通常这样做是为了节省内存。

最简单的解决方案是在扩展或收缩列表时制作副本。当您需要缩短或扩展您的列表时，创建一个目标大小的新列表，然后使用两个嵌套循环进行复制，就好像原始列表是一个 2D 数据结构一样。row制作一个接受 a 、 acolumn和 an的映射函数，N并将索引返回到与该{row, column}对对应的普通列表中可能非常有用：

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

现在，您可以将 size 列表中的一对索引转换{r, c}为 size 列表中N1同一对的索引N2。

您可以通过就地扩展和收缩来改进此解决方案。关键问题是你走的方向：收缩时，从前到后；展开时，从后向前。

于 2012-11-08T12:46:05.393 回答