Задача: 553. Optimal Division
Сложность: medium

Дано целочисленный массив nums. Соседние целые числа в nums будут выполнять деление с плавающей запятой.

Например, для nums = [2,3,4] мы будем вычислять выражение "2/3/4".
Однако, вы можете добавить любое количество скобок в любое место, чтобы изменить приоритет операций. Вы хотите добавить эти скобки так, чтобы значение выражения после вычисления было максимальным.

Верните соответствующее выражение, которое имеет максимальное значение в строковом формате.

Пример:

Input: nums = [1000,100,10,2]
Output: "1000/(100/10/2)"
Explanation: 1000/(100/10/2) = 1000/((100/10)/2) = 200
However, the bold parenthesis in "1000/((100/10)/2)" are redundant since they do not influence the operation priority.
So you should return "1000/(100/10/2)".
Other cases:
1000/(100/10)/2 = 50
1000/(100/(10/2)) = 50
1000/100/10/2 = 0.5
1000/100/(10/2) = 2

👨‍💻 Алгоритм:

1⃣Разверните оба числа. Инициализируйте массив ans с (N+M) нулями. Для каждой цифры во втором числе: держите переменную переноса, изначально равную 0. Инициализируйте массив (currentResult), начинающийся с некоторых нулей в зависимости от места цифры во втором числе.

2⃣Для каждой цифры первого числа: умножьте цифру второго числа на цифру первого числа и добавьте предыдущий перенос к результату умножения. Возьмите остаток от деления на 10, чтобы получить последнюю цифру. Добавьте последнюю цифру к массиву currentResult. Разделите результат умножения на 10, чтобы получить новое значение переноса.

3⃣После итерации по каждой цифре в первом числе, если перенос не равен нулю, добавьте перенос к массиву currentResult. Добавьте currentResult к массиву ans. Если последняя цифра в ans равна нулю, перед разворотом ans удалите этот ноль, чтобы избежать ведущего нуля в окончательном ответе. Разверните ans и верните его.

😎 Решение:

class Solution {
    private List<Integer> addStrings(List<Integer> num1, List<Integer> num2) {
        List<Integer> ans = new ArrayList<>();
        int carry = 0;
        int n1 = num1.size();
        int n2 = num2.size();

        for (int i = 0; i < Math.max(n1, n2) + 1; ++i) {
            int digit1 = i < n1 ? num1.get(i) : 0;
            int digit2 = i < n2 ? num2.get(i) : 0;
            int sum = digit1 + digit2 + carry;
            carry = sum / 10;
            ans.add(sum % 10);
        }
        return ans;
    }

    private List<Integer> multiplyOneDigit(String firstNumber, char secondNumberDigit, int numZeros) {
        List<Integer> currentResult = new ArrayList<>(Collections.nCopies(numZeros, 0));
        int carry = 0;

        for (char digit : firstNumber.toCharArray()) {
            int multiplication = (secondNumberDigit - '0') * (digit - '0') + carry;
            carry = multiplication / 10;
            currentResult.add(multiplication % 10);
        }
        if (carry != 0) {
            currentResult.add(carry);
        }
        return currentResult;
    }

    public String multiply(String firstNumber, String secondNumber) {
        if (firstNumber.equals("0") || secondNumber.equals("0")) {
            return "0";
        }

        firstNumber = new StringBuilder(firstNumber).reverse().toString();
        secondNumber = new StringBuilder(secondNumber).reverse().toString();

        List<Integer> ans = new ArrayList<>(Collections.nCopies(firstNumber.length() + secondNumber.length(), 0));

        for (int i = 0; i < secondNumber.length(); ++i) {
            ans = addStrings(multiplyOneDigit(firstNumber, secondNumber.charAt(i), i), ans);
        }

        while (ans.get(ans.size() - 1) == 0) {
            ans.remove(ans.size() - 1);
        }

        StringBuilder answer = new StringBuilder();
        for (int i = ans.size() - 1; i >= 0; --i) {
            answer.append(ans.get(i));
        }

        return answer.toString();
    }
}

Ставь 👍 и забирай 📚 Базу знаний