Java: возможные комбинации массива
Я работаю над проблемой Java:
Проблема:
Пользователь вводит массив целых чисел, размер массива может быть 1-9. Мне нужно переставить массив так, чтобы он выводил наибольшее значение, которое делится на 3. Мне не нужно использовать все целые числа в массиве.
Примеры:
Входы: (список целых) l = [3, 1, 4, 1]
Выход: (внутр.) 4311
Входы: (список целых) l = [3, 1, 4, 1, 5, 9]
Выход: (внутр.) 94311
-
Пока я потратил на это около 5 часов. Мой код работает, но он в значительной степени пробует каждую комбинацию, пока одна из них не сработает. Мне нужен более эффективный код.
Это мой код:
public class CodedMessage {
public static int zero = 0;
public static int one = 0;
public static int two = 0;
public static int three = 0;
public static int four = 0;
public static int five = 0;
public static int six = 0;
public static int seven = 0;
public static int eight = 0;
public static int nine = 0;
public static int best = 0;
public static int current = 0;
public static int newZero = 0;
public static int newOne = 0;
public static int newTwo = 0;
public static int newThree = 0;
public static int newFour = 0;
public static int newFive = 0;
public static int newSix = 0;
public static int newSeven = 0;
public static int newEight = 0;
public static int newNine = 0;
public static void main(String[] args) {
int[] myIntArray = {3,1,4,1};
System.out.println(answer(myIntArray));
}
public static int answer(int[] l) {
String line = "";
for (int c : l) {
line += c;
}
zero = line.length() - line.replace("0", "").length();
one = line.length() - line.replace("1", "").length();
;
two = line.length() - line.replace("2", "").length();
;
three = line.length() - line.replace("3", "").length();
;
four = line.length() - line.replace("4", "").length();
;
five = line.length() - line.replace("5", "").length();
;
six = line.length() - line.replace("6", "").length();
;
seven = line.length() - line.replace("7", "").length();
;
eight = line.length() - line.replace("8", "").length();
;
nine = line.length() - line.replace("9", "").length();
;
if (Integer.parseInt(line)%3 != 0) {
}else {
possibleStrings(l.length, l, "");
}
return best;
}
public static String possibleStrings(int maxLength, int[] alphabet, String curr) {
if (!curr.equals("")) {
current = Integer.parseInt(curr);
}
if (current > best) {
if (current % 3 == 0) {
String line = Integer.toString(current);
newZero = line.length() - line.replace("0", "").length();
newOne = line.length() - line.replace("1", "").length();
;
newTwo = line.length() - line.replace("2", "").length();
;
newThree = line.length() - line.replace("3", "").length();
;
newFour = line.length() - line.replace("4", "").length();
;
newFive = line.length() - line.replace("5", "").length();
;
newSix = line.length() - line.replace("6", "").length();
;
newSeven = line.length() - line.replace("7", "").length();
;
newEight = line.length() - line.replace("8", "").length();
;
newNine = line.length() - line.replace("9", "").length();
;
if (zero >= newZero && one >= newOne && two >= newTwo && three >= newThree && four >= newFour
&& five >= newFive && six >= newSix && seven >= newSeven && eight >= newEight
&& nine >= newNine) {
best = current;
}
}
}
if (curr.length() == maxLength) {
if (!curr.equals("") &&Integer.parseInt(curr)%3 != 0) {
return "hi";
}
} else {
for (int i = 0; i < alphabet.length; i++) {
String oldCurr = curr;
curr += alphabet[i];
possibleStrings(maxLength, alphabet, curr);
curr = oldCurr;
}
}
return "hi";
}
}Может кто-нибудь сделать его более эффективным, я пытался, но не смог.
Спасибо!
Ответы 2
Чтобы число делилось на 3, необходимо, чтобы сумма цифр делилась на 3. Вы можете сделать это так:
Отсортируйте цифры.
Используйте отсортированные цифры, чтобы найти группу с наибольшим количеством цифры. Сделайте это, сначала проверив, делится ли общая сумма на 3. Затем попробуйте с n-1 наибольшими цифрами и так далее. Первая группа, которую вы найдете, - это то, что вы ищете
Обновлено: на основе предложения в комментариях
Для второго шага.
Найдите k=sum%3;
if (k==0) у вас есть решение.
Если нет, то проверьте все цифры, начиная с младшего (конца массива) if digit%3=k. Если да, удалите его, и вы найдете решение.
Если ни одна цифра этого не делает, попробуйте использовать 2 цифры, 3 цифры и так далее.
В этом есть проблема, допустим, что массив состоит из 9 цифр, на то, чтобы опробовать каждую комбинацию, потребовалось бы очень много времени. Мне нужен быстрый способ сделать это.
Вы не будете пробовать каждую комбинацию. В худшем случае вы попробуете каждую «Группу» комбинаций. Например: у вас есть группа из 8 цифр, где сумма делится на 3. Их 8! комбинации в этой группе, но вы не будете пробовать ни одну из этих 40320. У вас есть отсортированные цифры, и вы можете найти номер прямо оттуда. В моем решении программа будет проверять только комбинации. 2 * (C9,9 + c9,8 + C9,7 + C9,6 + C9,5) = 2 (1 + 9 + 36 + 84 + 126) = 512 комбинаций МАКС. Но вы можете остановиться, как только найдете одну группу, которая делится на 3, при условии, что вы правильно выберете порядок.
Я не понимаю, можете ли вы прислать фрагмент кода?
@MBo Вы имеете в виду, сначала проверьте, есть ли число a% 3 = k.
@Kristjan Kica Да, это более правильно. Удаляю комментарий и добавлю новый
k = digitsum% 3. Найдите наименьшее a: a %3 = k Если такой a существует в массиве, это решение. Если нет - найдите наименьшую пару (a + b)% 3 = k. Если такой пары нет, ищите тройку и так далее.
Вам просто нужно отсортировать массив по убыванию чисел и записать их в одну строку. Решит ли это проблему?
Нет, не будет, потому что вам не нужно использовать все целые числа в массиве int.
Входные данные: (int list) l = [3, 1, 4, 1, 5, 9] Выход: (int) 94311 Я не использую 5 из входного массива
Я действительно не знаю, что вы пытаетесь сделать в своем коде, но если я правильно понял вашу проблему, все, что вам нужно сделать, это сначала найти все комбинации четырех цифр, которые в сумме составляют число, которое делится на 3. Затем найдите самый большой.