Подходы к тому, как разделить список
Все объекты гарантированно имеют метод .equals(), поскольку Object содержит метод, .equals(), который возвращает логическое значение. Задача подкласса переопределять этот метод, если требуется дополнительное определение определения. Без него (т. Е. Используя ==) только адреса памяти проверяются между двумя объектами для равенства. String переопределяет этот метод .equals() и вместо использования адреса памяти возвращает сравнение строк на уровне символа для равенства.
Ключевое замечание состоит в том, что строки хранятся в одном пуле, поэтому после создания строки он всегда хранится в программе по тому же адресу. Строки не меняются, они неизменяемы. Вот почему это плохая идея использовать регулярную конкатенацию строк, если у вас есть серьезное количество обработки строк. Вместо этого вы будете использовать предоставленные классы StringBuilder. Помните, что указатели на эту строку могут измениться, и если вам было интересно увидеть, были ли два указателя одинаковыми ==, это был бы прекрасный способ. Строки сами не делают.
1 ответ
Вы уверены, что вы нашли контрпримеры? Моя математика может быть неправильной, но кажется, что невозможно составить такой список. Заметим, что для списка из трех элементов a <= b <= c мы можем разделить их так же [a, b], [c]. Это потому, что для a + b, чтобы быть больше чем 2/3 суммы, у нас было бы (a + b) * 3 > 2 * (a + b + c) или a + b > 2 * c, что означает, что a и / или b должно быть больше, чем c .
Имея это в виду, мы группируем наши числа в три ячейки, каждая из которых такова, что ее сумма меньше, чем N/2. Обратите внимание, что если бы у нас было четыре элемента a <= b <= c <= d, мы могли бы разделить их как [a, b], [c], [d]. Повторяя логику, как и раньше, для того, чтобы a + b был больше, чем N/2, нам потребовалось бы (a + b) * 2 > (a + b + c + d) или a + b > c + d, что означает, что a и / или b должны быть больше, чем c.
Мы можем бесконечно повторять эту логику отсюда. Принимая наш список за x, чтобы a + b был больше, чем N/2, нам понадобится (a + b) * 2 > sum(x), что невозможно для списка с 2 или большим количеством элементов, которые больше, чем a и [ 1124] (что относится ко всем спискам длиной 4 и более).
Применяя эту рекурсивную логику, мы можем построить путь от n до трех бинов, рассматривать их как числа a, b, c из первого абзаца и строить наш ответ таким образом.
Алгоритмически, создайте группу узлов, содержащих каждый элемент в массиве (как список длины один), и сумму (на данный момент равную самому элементу). Вставьте их в кучу мин, с суммой в качестве ключа. Поместите мин два, объедините их (объедините списки элементов, добавьте суммы) и вставьте обратно в кучу мин. Промойте и повторяйте, пока у вас есть два узла в куче. Теперь они содержат ваше решение.