Блог

Я пытаюсь использовать код для печати самой длинной возрастающей подпоследовательности, код работает, но он не печатает правильную самую длинную возрастающую подпоследовательность.

например, если входные данные были: 3,5,11,8,4,7,1,2,10,12,9,6

Вывод : [1, 2, 6, 9, 12]

мой желаемый результат: 3,4,7,10,12

Я отладил способ вставки и печати arraylist и его исправления, я считаю, что здесь есть что-то неправильное, почему это было неправильно?почему это меняет порядок чисел !?

 public static ArrayList<Integer> lengthOfsequance(ArrayList<Integer> nums) {

    if (nums == null || nums.size() == 0)
        return null;
    ArrayList<Integer> list = new ArrayList<Integer>();
    for (int num : nums) 
    {
        if (list.size() == 0 || num > list.get(list.size() - 1)) 
            list.add(num);
        else
        {
            int i = 0;
            int j = list.size() - 1;
            while (i < j) 
            {
                int mid = (i   j) / 2;
                if (list.get(mid) < num) 
                    i = mid   1;
                else
                    j = mid;
            }
           list.set(j, num);
        }
    }
    return list;
}
  

Ваш подход не может работать. Вы используете один список для сбора самой длинной последовательности. Но ваша входная последовательность может иметь несколько возрастающих последовательностей. Может быть, тот, который идет от индекса 0 до 5; и другой, который идет от индекса 10 до 20.

Другими словами; вам нужна другая стратегия; и «прямой» подход — это что-то вроде:

1. повторите список входных данных, чтобы «собрать» все возрастающие последовательности (другими словами: это будет список списков).
2. После этого вы просматриваете этот список списков, чтобы найти максимальную длину

Конечно, затем это можно дополнительно оптимизировать — вам не нужно запоминать все возрастающие последовательности, вам просто нужно помнить о «самой длинной завершенной» последовательности, которую вы видели раньше.

Но, как уже было сказано: первой, наивной реализацией было бы просто идентифицировать все последовательности «увеличение завершение» во входном списке. И затем вы прокладываете свой путь оттуда.

(поскольку я предполагаю, что это какой-то проект домашнего задания, я только даю руководящие идеи, а не исходный код. Реализация оставлена в качестве упражнения для читателя)

Редактировать: для решения комментария «как избежать запоминания «равных» последовательностей».

Предположим, что ваш ввод — это такая последовательность: 1,2,3,0,1,2,3,4,1,2,3 Когда вы ищете там возрастающие последовательности, вы должны найти:

(1, 2, 3) и (0, 1, 2, 3, 4), и (1, 2, 3)

Вы правы: если вы представляете вышеупомянутые кортежи как List<Integer> ; тогда «правильный» код будет собирать три списка; где первый и третий будут равны (потому что они содержат одинаковые числа).

И когда вы сохраняете эти списки внутри List<List<Integer>> , да, ваш код должен учитывать дубликаты. Одним из способов избежать этого может быть использование a Set<List<Integer>> вместо — потому что Set по своей природе гарантирует, что все записи, хранящиеся в этой коллекции, не равны. Другими словами: когда вы добавляете два списка с одинаковым содержимым в объект Set, тогда, в конце концов, набор будет содержать только один из этих двух списков. (следует помнить одну вещь — когда вы используете здесь HashSet , порядок операций добавления теряется).

Наконец: вместо использования Set<List<Integer>> вы могли бы также использовать a Map<Integer, Integer> с «ключом», являющимся длиной последовательности; и «значение», являющееся первым индексом в списке ввода.

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

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