Есть ли алгоритм для этого случая [duplicate]

Фон

Все объекты Java имеют метод toString(), который вызывается при попытке и печати объекта.

System.out.println(myObject);  // invokes myObject.toString()

Этот метод определен в классе Object (суперкласс всех объектов Java). Метод Object.toString() возвращает довольно уродливую строку, состоящую из имени класса, символа @ и hashcode объекта в шестнадцатеричном формате. Код для этого выглядит так:

// Code of Object.toString()
public String toString() {
    return getClass().getName() + "@" + Integer.toHexString(hashCode());
}

Результат, такой как com.foo.MyType@2f92e0f4, можно поэтому объяснить следующим образом:

  • com.foo.MyType - имя класса, т.е. класс MyType в пакете com.foo.
  • @ - присоединяет строку вместе
  • 2f92e0f4 хэш-код объекта.

Название классов массивов выглядит немного иначе, что хорошо объясняется в Javadocs для Class.getName() . Например, [Ljava.lang.String означает:

  • [ - одномерный массив (в отличие от [[ или [[[ и т. Д.)
  • L - массив содержит класс или интерфейс
  • java.lang.String - тип объектов в массиве

Настройка вывода

Чтобы напечатать что-то другое, когда вы вызываете System.out.println(myObject), вы должны переопределить метод toString() в своем классе. Вот простой пример:

public class Person {

  private String name;

  // constructors and other methods omitted

  @Override
  public String toString() {
    return name;
  }
}

Теперь, если мы напечатаем Person, мы увидим их имя, а не com.foo.Person@12345678.

Имейте в виду, что toString() один способ для объекта, который должен быть преобразован в строку. Как правило, этот вывод должен полностью описывать ваш объект в ясной и сжатой форме. Лучше toString() для нашего класса Person может быть:

@Override
public String toString() {
  return getClass().getSimpleName() + "[name=" + name + "]";
}

Который напечатал бы, например, Person[name=Henry]. Это действительно полезная часть данных для отладки / тестирования.

Если вы хотите сосредоточиться только на одном аспекте своего объекта или включить много jazzy-форматирования, вам может быть лучше определить отдельный метод, например String toElegantReport() {...}.


Автоматическое создание выхода

Многие [ID5] предлагают поддержку для автоматического создания метода toString() на основе полей в классе. Например, см. Документы для Eclipse и IntelliJ .

Некоторые популярные библиотеки Java также предлагают эту функцию. Некоторые примеры включают в себя:


Печать групп объектов

Итак, вы создали приятный toString() для своего класса. Что происходит, если этот класс помещается в массив или коллекцию?

Массивы

Если у вас есть массив объектов, вы можете вызвать Arrays.toString() для создания простого представления содержимого массива. Например, рассмотрим этот массив объектов Person:

Person[] people = { new Person("Fred"), new Person("Mike") };
System.out.println(Arrays.toString(people));

// Prints: [Fred, Mike]

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

Если у вас многомерный массив, вы можете использовать Arrays.deepToString() для достижения такого же вывода.

Коллекции

В большинстве коллекций будет выдаваться хороший вывод, основанный на вызове .toString() для каждого элемента.

List people = new ArrayList<>();
people.add(new Person("Alice"));
people.add(new Person("Bob"));    
System.out.println(people);

// Prints [Alice, Bob]

Поэтому вам просто нужно убедиться, что элементы списка определяют nice toString(), как обсуждалось выше.

7
задан John 12 October 2012 в 17:43
поделиться

3 ответа

Вычислить все возможные значения для a_w + a_x, вставить их в хэш-таблицу. Вставьте (a_w + a_x, w) и (a_w + a_x, x) во вторую хеш-таблицу.

Прежде чем вставлять значение в первую хеш-таблицу, проверьте, уже ли она в таблице. Если да, проверьте вторую таблицу. Если есть один из (a_w + a_x, w) или (a_w + a_x, x), не вставляйте ничего (у нас есть дублирующий элемент). Если ни одна из этих пар не во второй таблице, у нас есть положительный ответ.

Если после обработки всех (w, x) пар у нас нет положительного ответа, это означает, что нет такие попарно отличающиеся индексы.

Сложность по времени - O (n2). Требования к пространству также O (n2).

В этом случае можно сделать то же самое в O (n) пространстве, но O (n2 * log (n)) время со слегка модифицированным алгоритмом из этого ответа: Сумма-подмножество с фиксированным размером подмножества :

  1. Сортировка списка.
  2. Используйте очередь приоритетов для элементов, содержащую a_w + a_x в качестве ключа и w, x в качестве значений. Предварительно заполните эту очередь элементами n-1, где x = 0 и w = 1 .. n-1.
  3. Повторно введите минимальный элемент (sum, w, x) из этой очереди и поместите элемент (a_w + a_x_plus_1, w, x+1) в queue (но не ставьте элементы при x> = w). Остановитесь, когда два последовательных элемента, удаленные из очереди, имеют одинаковую сумму.
  4. Чтобы обрабатывать дубликаты, можно сравнить w, x двух последовательных элементов, имеющих равную сумму. Но легче использовать кримампани для предварительной обработки. Если отсортированный список содержит две пары дубликатов или один элемент дублируется 4 раза, успех. В противном случае дублируется не более одного значения; оставьте в списке только один экземпляр и добавьте его удвоенное значение в очередь приоритетов вместе со «специальной» парой индексов: (2a, -1, -1).
4
ответ дан Community 24 August 2018 в 17:23
поделиться

Если у вас 8,5 ГБ памяти (больше для unsigned ints, меньше, если суммы или индексы не охватывают весь диапазон int), создайте три массива. Сначала используется 1 бит на каждую возможную сумму. Это растровое изображение результатов. Второй использует 32 бита на каждую возможную сумму. Он записывает индекс j. Третья использует 1 бит на каждую возможную сумму. Это битовое поле, которое записывает, была ли эта сумма встречена в текущей итерации i - нуль с каждой итерацией. Итерация i = 0 ... n и j = i + 1 ... n. Для каждой суммы см., Если она установлена ​​в первом битовом поле (если оно было встречено раньше). Если это так, посмотрите, соответствует ли индекс, записанный во 2-м массиве, либо i, либо j (если старый j соответствует либо новому i, либо новому j). Если это не так, убедитесь, что бит в 2-м массиве установлен (если он был установлен в текущей итерации, поэтому старый i соответствует новому i). Если это не так, у вас есть матч! (Старый я никогда не буду сопоставлять старый j или новый j, а новый i никогда не будет соответствовать новому j.) Выход. В противном случае запишите сумму во всех трех массивах и продолжайте.

Хотя она использует память на 40 долларов (я люблю настоящее :), это, вероятно, намного быстрее, чем использование хеш-карт и бокса. Может даже использовать меньше памяти для больших n. Один недостаток данных почти никогда не будет в кэше L2. Но постарайтесь установить JVM для использования огромных страниц, так что по крайней мере промах TLB тоже не пойдет в основную память. Это o (n ^ 2) для обработки и o (1) для памяти.

0
ответ дан Aleksandr Dubinsky 24 August 2018 в 17:23
поделиться

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

Сначала мы используем хэш-таблицу для подсчета частоты каждого элемента в исходном массиве. Если хотя бы 2 элемента имеют дубликаты (их частота не менее 2) или если элемент имеет частоту не менее 4, то ответ будет true. В противном случае, если элемент a встречается с частотой 2 или 3, мы добавляем 2a во вторую хеш-таблицу и заменяем все копии a на одну копию в исходном массиве.

Затем в модифицированном массиве для каждой пары индексов i, j с i < j мы добавим a_i + a_j во вторую хэш-таблицу и вернем true, если найдем дубликат запись в этой хэш-таблице.

3
ответ дан krjampani 24 August 2018 в 17:23
поделиться
Другие вопросы по тегам:

Похожие вопросы: