Задача: 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 и верните его.

😎 Решение:

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    private List<int> AddStrings(List<int> num1, List<int> num2) {
        var ans = new List<int>();
        int carry = 0;
        int n1 = num1.Count;
        int n2 = num2.Count;

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

    private List<int> MultiplyOneDigit(string firstNumber, char secondNumberDigit, int numZeros) {
        var currentResult = new List<int>(new int[numZeros]);
        int carry = 0;

        foreach (char digit in firstNumber) {
            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 == "0" || secondNumber == "0") {
            return "0";
        }

        firstNumber = new string(firstNumber.Reverse().ToArray());
        secondNumber = new string(secondNumber.Reverse().ToArray());

        var ans = new List<int>(new int[firstNumber.Length + secondNumber.Length]);

        for (int i = 0; i < secondNumber.Length; ++i) {
            ans = AddStrings(MultiplyOneDigit(firstNumber, secondNumber[i], i), ans);
        }

        while (ans.Last() == 0) {
            ans.RemoveAt(ans.Count - 1);
        }

        var answer = new System.Text.StringBuilder();
        for (int i = ans.Count - 1; i >= 0; --i) {
            answer.Append(ans[i]);
        }

        return answer.ToString();
    }
}

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