Проблема в том, что я нахожу наибольшее число, которое вы можете «сделать» из нескольких чисел?

Question

Пример ввода:

4
123 124 56 90

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

Итак, возможные комбинациидля этих чисел {1231245690, 1241235690, 5612312490, 9012312456, 9056124123 и т. д.}, причем наибольшее число составляет 9056124123.

Я думаю об этой проблеме следующим образом: наибольшее число начинается с самого большогопоследняя цифра в наборе.Таким образом, наибольшее число здесь будет начинаться с «9», поэтому 90 - это первое число, которое меня интересует.Затем я смотрю на остальную часть набора с самой большой последней цифрой, которая будет «5», поэтому 56 - это второе число, которое меня интересует.Если наибольшая последняя цифра является ничьей, я оценил бы вторую-последнюю цифру и т. Д.

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

Answer 1

Вы почти на правильном пути.Нет необходимости в битовых манипуляциях.Достаточно отсортировать их с помощью пользовательской функции сравнения строк, как показано ниже.

Collections.sort(inputArray, new Comparator < String > () {
 public int compare(String a, String b) {
  //if a = "80", b = "807"
  String ab = a + b; // 80807
  String ba = b + a; //80780
  // now compare
  return ab.compareTo(ba) > 0 ? -1 : 1;
 }
});

, а затем объединить их.

@ Дауд ибн Карим Спасибо, что указали на край.

Answer 2

Тщательно изучите, где находятся цифры в выходных данных.90 56 124 123 Числа идут от наибольших к наименьшим, в зависимости от того, какая самая большая цифра слева.(Самая большая первая цифра - @Mark)

Существуют возможные входы, которые требуют разрыва связи.С учетом чисел '80, 807 и 000 '

Сравните их слева направо.

8 0
| |\
8 0 7

Поскольку 807 длиннее 80, сравните последний бит 807 (7) с80.

7
|
8 0

Сравнение завершено, потому что 8 из 80 сравнивалось с 7 из 807, показывая, что 80 должно быть первым.Сложите 80 и 807 вместе и получите 80807 и, конечно, добавьте 000.

Answer 3

Преобразование чисел в строки, добавление к ним "X" справа, чтобы сделать их одинаковой длины, сортировка по убыванию, объединение, удаление "X", ваш результат.

Answer 4

Вы на правильном пути!

Проще всего разбираться в типах - это превращать числа в строки.Это позволяет быстро получить доступ к первой, второй, ... цифре исходных чисел.И конкатенация также намного проще сделать для строк!