java - 简单的 Java 列表问题

Question

我应该创建一个迭代方法 stretch，它将正数 n 作为参数并返回一个新的 ListItem，该列表项开始一个列表，其中原始列表中的每个数字都重复 n 次。例如，如果原始列表为( 6 7 6 9 )，参数值为2，则返回的新列表为( 6 6 7 7 6 6 9 9 )。

我已经有一个 listitem 构造函数，它具有该节点的值和对下一个节点的引用:

   ListItem(int number, ListItem next) {
        this.number = number;
        this.next   = next;
}

我的代码是这样的:

    public ListItem stretch(int n) {
        //make an array of list items that is n times bigger than the original one.
        ListItem[] newList = new ListItem[this.length() * n];

    //Then loop through the old list one value at a time. At each value do a second loop n times to stretch

        int index = 0;
        int counter = 0;
        for(int i = 0; i < this.length(); i++){
            while(counter++ < n){
                newList[index++] = this[i];*************************
        }
        return newList;****************
    }

}

有两个问题点，我在其中加了星号。我应该返回一个列表项，但 NewList 是一个数组。 而且我不确定第一个加星标的行有什么问题。

如有任何帮助/指导，我们将不胜感激。

Answer 1

解决这个问题的最好方法是画一些图。然后尝试将问题分解为子问题。让我们从简单的情况开始:长度为 2 的列表:

ListItem two = new ListItem(1, ListItem(2, null));

这是一张照片

two = ( number == 1
      ( next   == ( number == 2
                  ( next   == null

这是另一张图片:

+---+  +---+    The "/" here is the "null" above, which terminates the list.
| 1 |->| 2 |-/  
+---+  +---+    

Think of it this way: a list consists of a first ListItem, which points to the rest of the list via "next". The empty list, then is null and the "next" of the last ListItem is always empty. (null).

Now what's really going on when we're asked to "stretch" a list? Say, by 2?

Well, the empty list is easy, it doesn't change. But it's also irrelevant since null.stretch() will end badly in the language you're using. The list of length 1 then is our simplest practical case:

we have:

we have       we want

+---+         +---+   +---+
| 1 |-/       | 1 |-->| 1 |-/
+----         +---+   +---+

Ok, that's not so hard. We already have a list of length one. All we need to do hang it off the next of a new ListItem and we'll have a list of length two. Clearly we need the ability to add something to an existing list. Adding it to the front is easiest, so we'll define a little helper for that:

ListItem addItemToFront(int number) {
    return new ListItem(number, this);
} 

好的，现在让我们编写代码并将其命名为 stretchFirstItemByOne:

ListItem stretchFirstItemByOne() {           
    return this.addItemToFront(this.number); 
}

You'll see me use this.something() a lot in these examples, though it isn't necessary. I'm just trying to be clear that these are method calls on the current object (this).

但是，假设我们想拉伸(stretch)一些更大的n？您已经尝试过——有点不幸地——使用上面的 for 循环。你可以那样做。但我会采取不同的方式。

ListItem stretchFirstItem(n) {
    if (n == 1)      // stretching to length 1 means nothing
        return this; // to do. just return this.
    else {
        // well, if we stretch our item to length n-1 first
        // then all we have to do is stretch it by one and
        // we're done.
        return this.stretchFirstItem(n-1).stretchFirstItemByOne(); 
    }
}

停下来想一想。如果遇到问题，请将其重写为 for 循环。

这一切都很好，您可能会说，但它只能处理长度为 1 的列表。多么真实，多么真实。

假设您有一个长度为 3 的列表，并且您想将其拉伸(stretch) 2。

  +---+  +---+  +---+
( | 1 |->| 2 |->| 3 |-/ ).stretch(2)
  +---+  +---+  +---+

Tough? Well, we can get started at least. We know how to handle things if the list has only one item:

ListItem stretch(int n) {
    ListItem restOfList = this.next;
    if (restOfList == null) { // this list has length one
        return this.stretchFirstItem(n);
    } else {
        // if we had the rest of the list stretched, then we could
        // add this.number to the front of this stretched list, stretch
        // that first item and then we'd be done.
    }
}

嘿，但是 stretch 不应该为我们做这件事吗，你知道，拉伸(stretch)整个列表？难道我们不能用它来扩展列表的其余部分，这样我们就可以做一些简单的事情来扩展第一项吗？但我们甚至还没有写完拉伸(stretch)——我的意思是——它不起作用。没那么容易，不是吗？可以吗？

ListItem stretch(int n) {
    ListItem restOfList = this.next;
    if (restOfList == null) { // this list has length one
        return this.stretchFirstItem(n);
    } else {
        return restOfList     //-------------------------
           .magic(...)        // Left as an exercise for
           .moreMagic(...)    // the reader.
           .zyzzy(...);       //-------------------------
    }
}