Простой вопрос списка 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 |-/  
+---+  +---+    

Думайте об этом так: список состоит из первого ListItem, который указывает на остальную часть списка через «next». Пустой список, тогда является нулем, и "следующий" из последнего ListItem всегда пуст. (Нуль).

Теперь, что на самом деле происходит, когда нас просят «растянуть» список? Скажем, на 2?

Ну, пустой список прост, он не меняется. Но это также не имеет значения, поскольку null.stretch() плохо кончится на языке, который вы используете. Список длины 1 в нашем простейшем практическом случае:

у нас есть:

we have       we want

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

Хорошо, это не так сложно. У нас уже есть список длины один. Все, что нам нужно сделать, это повесить его на следующий новый элемент ListItem, и у нас будет список длиной два. Очевидно, нам нужна возможность добавить что-то в существующий список. Добавить его в начало проще всего, поэтому для этого мы определим небольшого помощника:

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

Хорошо, теперь давайте закодируем это и назовем его stretchFirstItemByOne:

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

Вы увидите, что я часто использую this.something () в этих примерах, хотя это не обязательно. Я просто пытаюсь понять, что это вызовы метода для текущего объекта (this).

Но, предположим, мы хотим растянуть на несколько больших 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, если у вас возникли проблемы.

Это все очень хорошо, вы могли бы сказать, но он обрабатывает только списки длины один. Как верно, как верно.

Предположим, у вас есть список длины 3, и вы хотите растянуть его на 2.

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

Tough? Ну, мы можем начать по крайней мере. Мы знаем, как обращаться с вещами, если в списке есть только один элемент:

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.
    }
}

Эй, но разве растянуть не должно это сделать для нас, вы знаете, растянуть целые списки? Разве мы не можем использовать это, чтобы растянуть остальную часть списка, чтобы мы могли немного упростить и растянуть первый элемент? Но мы еще не закончили писать - я имею в виду - это не работает. Это не могло быть так просто, не так ли? Может ли это?

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(...);       //-------------------------
    }
}

Answer 2

Домашнее задание

Похоже, вы должны создавать связанный список, но вместо этого вы создаете массив ListItems. Массив ListItems не является плохим , но вам необходимо указать следующее значение каждого элемента ListItem на следующем элементе в списке.

Тогда последняя строка вашей функции вернет первый элемент в списке.

Answer 3

Проблема с первой строкой состоит в том, что, поскольку this не является массивом, вы не можете подписать его ([i]). Я не могу помочь вам с этой проблемой без более подробной информации о вашем классе ListItem. Вы делаете связанный список?

Для возврата вы, вероятно, захотите вернуть первый элемент в массиве. Если это так, измените его на return newList[0]. Если вы хотите вернуть массив, измените функцию, чтобы он возвращал массив, например: public ListItem[] stretch(.

Answer 4

Первая помеченная строка, безусловно, неверна, но это не ваша проблема, если вы подумаете об этом: вас не просят вернуть массив в первую очередь.

Проблема о том, как вернуть ListItem, должна решиться сама собой, если вы рассмотрите, как на самом деле выглядит ваш ввод: возьмите лист бумаги и нарисуйте его, и вы поймете, почему достаточно возврата одного элемента списка, и что сделать на ListItem, чтобы каждый элемент удвоился.