Java: возможные комбинации массива

Question

Я работаю над проблемой Java:

Проблема:

Пользователь вводит массив целых чисел, размер которого может быть 1-9.Мне нужно переставить массив так, чтобы он печатал наибольшее значение, которое делится на 3. Мне не нужно использовать все целые числа в массиве.

Примеры:

Входные данные: (int list) l = [3, 1, 4, 1]

Выход: (int) 4311

Входы: (int list) l = [3, 1, 4, 1, 5, 9]

Вывод: (int) 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";
	}

}

Может кто-нибудь сделать его более эффективным, я пытался, но не смог.

Спасибо!

Answer 1

Вам просто нужно отсортировать массив в порядке убывания чисел и записать их в одну строку.Решит ли это проблему?

Answer 2

Чтобы число делилось на 3, необходимо, чтобы сумма цифр была кратна 3. Вы можете сделать это следующим образом:

1. Сортировать цифры.

2. Используйте отсортированные цифры, чтобы найти группу с наибольшим количеством цифр.Сделайте это, сначала проверив, делится ли общая сумма на 3. Затем попробуйте ввести n-1 больших цифр и так далее.Первая группа, которую вы найдете, это то, что вы ищете

Редактировать: на основе предложения в комментариях Для второго шага.Найдите k=sum%3;

if(k==0) у вас есть решение.

Если нет, то проверьте все цифры, начиная с самого нижнего (конец массива) if digit%3=k.Если это так, удалите его, и вы найдете решение.Если ни одна цифра не делает этого, попробуйте ввести 2 цифры, 3 цифры и т. Д.