Даны два неотрицательных целых числа num1 и num2, представленные в виде строк. Верните произведение num1 и num2, также представленное в виде строки.
Примечание: Вы не должны использовать встроенную библиотеку BigInteger или прямо преобразовывать входные данные в целые числа.
Пример:
Input: num1 = "2", num2 = "3"
Output: "6"
C# решение
сопоставлено/оригиналclass Solution {
private List<int> AddStrings(List<int> num1, List<int> num2) {
List<int> ans = new List<int>();
int carry = 0;
for (int i = 0; i < num1.Count || i < num2.Count || carry != 0; ++i) {
int digit1 = i < num1.Count ? num1[i] : 0;
int digit2 = i < num2.Count ? num2[i] : 0;
int sum = digit1 + digit2 + carry;
carry = sum / 10;
ans.Add(sum % 10);
}
if (carry != 0) {
ans.Add(carry);
}
return ans;
}
private List<int> MultiplyOneDigit(StringBuilder firstNumber, char secondNumberDigit, int numZeros) {
List<int> currentResult = new List<int>(new int[numZeros]);
int carry = 0;
for (int i = 0; i < firstNumber.Length; ++i) {
int multiplication = (secondNumberDigit - '0') * (firstNumber[i] - '0') + carry;
carry = multiplication / 10;
currentResult.Add(multiplication % 10);
}
if (carry != 0) {
currentResult.Add(carry);
}
return currentResult;
}
public string Multiply(string num1, string num2) {
if (num1 == "0" || num2 == "0") {
return "0";
}
StringBuilder firstNumber = new StringBuilder(new string(num1.Reverse().ToArray()));
StringBuilder secondNumber = new StringBuilder(new string(num2.Reverse().ToArray()));
int N = firstNumber.Length + secondNumber.Length;
List<int> ans = new List<int>(new int[N]);
for (int i = 0; i < secondNumber.Length; ++i) {
ans = AddStrings(MultiplyOneDigit(firstNumber, secondNumber[i], i), ans);
}
if (ans[ans.Count - 1] == 0) {
ans.RemoveAt(ans.Count - 1);
}
StringBuilder answer = new StringBuilder();
for (int i = ans.Count - 1; i >= 0; --i) {
answer.Append(ans[i]);
}
return answer.ToString();
}
}C++ решение
auto-draft, проверить перед отправкой#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
private List<int> AddStrings(List<int> num1, List<int> num2) {
List<int> ans = new List<int>();
int carry = 0;
for (int i = 0; i < num1.size() || i < num2.size() || carry != 0; ++i) {
int digit1 = i < num1.size() ? num1[i] : 0;
int digit2 = i < num2.size() ? num2[i] : 0;
int sum = digit1 + digit2 + carry;
carry = sum / 10;
ans.push_back(sum % 10);
}
if (carry != 0) {
ans.push_back(carry);
}
return ans;
}
private List<int> MultiplyOneDigit(StringBuilder firstNumber, char secondNumberDigit, int numZeros) {
List<int> currentResult = new List<int>(new int[numZeros]);
int carry = 0;
for (int i = 0; i < firstNumber.size(); ++i) {
int multiplication = (secondNumberDigit - '0') * (firstNumber[i] - '0') + carry;
carry = multiplication / 10;
currentResult.push_back(multiplication % 10);
}
if (carry != 0) {
currentResult.push_back(carry);
}
return currentResult;
}
public string Multiply(string num1, string num2) {
if (num1 == "0" || num2 == "0") {
return "0";
}
StringBuilder firstNumber = new StringBuilder(new string(num1.Reverse().ToArray()));
StringBuilder secondNumber = new StringBuilder(new string(num2.Reverse().ToArray()));
int N = firstNumber.size() + secondNumber.size();
List<int> ans = new List<int>(new int[N]);
for (int i = 0; i < secondNumber.size(); ++i) {
ans = AddStrings(MultiplyOneDigit(firstNumber, secondNumber[i], i), ans);
}
if (ans[ans.size() - 1] == 0) {
ans.RemoveAt(ans.size() - 1);
}
StringBuilder answer = new StringBuilder();
for (int i = ans.size() - 1; i >= 0; --i) {
answer.Append(ans[i]);
}
return answer.ToString();
}
}Java решение
сопоставлено/оригиналclass Solution {
private ArrayList<Integer> addStrings(
ArrayList<Integer> num1,
ArrayList<Integer> num2
) {
ArrayList<Integer> ans = new ArrayList<>();
int carry = 0;
for (int i = 0; i < num1.size() || i < num2.size(); ++i) {
int digit1 = i < num1.size() ? num1.get(i) : 0;
int digit2 = i < num2.size() ? num2.get(i) : 0;
int sum = digit1 + digit2 + carry;
carry = sum / 10;
ans.add(sum % 10);
}
if (carry != 0) {
ans.add(carry);
}
return ans;
}
ArrayList<Integer> multiplyOneDigit(
StringBuilder firstNumber,
char secondNumberDigit,
int numZeros
) {
ArrayList<Integer> currentResult = new ArrayList<>();
for (int i = 0; i < numZeros; ++i) {
currentResult.add(0);
}
int carry = 0;
for (int i = 0; i < firstNumber.length(); ++i) {
char firstNumberDigit = firstNumber.charAt(i);
int multiplication =
(secondNumberDigit - '0') * (firstNumberDigit - '0') + carry;
carry = multiplication / 10;
currentResult.add(multiplication % 10);
}
if (carry != 0) {
currentResult.add(carry);
}
return currentResult;
}
public String multiply(String num1, String num2) {
if (num1.equals("0") || num2.equals("0")) {
return "0";
}
StringBuilder firstNumber = new StringBuilder(num1);
StringBuilder secondNumber = new StringBuilder(num2);
firstNumber.reverse();
secondNumber.reverse();
int N = firstNumber.length() + secondNumber.length();
ArrayList<Integer> ans = new ArrayList<>();
for (int i = 0; i < N; ++i) {
ans.add(0);
}
for (int i = 0; i < secondNumber.length(); ++i) {
ans = addStrings(
multiplyOneDigit(firstNumber, secondNumber.charAt(i), i),
ans
);
}
if (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();
}
}JavaScript решение
сопоставлено/оригиналlet addStrings = function (num1, num2) {
let ans = [];
let carry = 0;
for (let i = 0; i < num1.length || i < num2.length; ++i) {
let digit1 = i < num1.length ? num1[i] : 0;
let digit2 = i < num2.length ? num2[i] : 0;
let sum = digit1 + digit2 + carry;
carry = Math.floor(sum / 10);
ans.push(sum % 10);
}
if (carry) {
ans.push(carry);
}
return ans;
};
let multiplyOneDigit = function (firstNumber, secondNumberDigit, numZeros) {
let currentResult = [];
for (let i = 0; i < numZeros; ++i) {
currentResult.push(0);
}
let carry = 0;
for (let i = 0; i < firstNumber.length; ++i) {
let multiplication = Number(secondNumberDigit) * Number(firstNumber[i]) + carry;
carry = Math.floor(multiplication / 10);
currentResult.push(multiplication % 10);
}
if (carry) {
currentResult.push(carry);
}
return currentResult;
};
let multiply = function (num1, num2) {
if (num1 === "0" || num2 === "0") {
return "0";
}
let firstNumber = [...num1];
let secondNumber = [...num2];
firstNumber.reverse();
secondNumber.reverse();
let N = firstNumber.length + secondNumber.length;
let ans = new Array(N).fill(0);
for (let i = 0; i < secondNumber.length; ++i) {
ans = addStrings(
multiplyOneDigit(firstNumber, secondNumber[i], i),
ans,
);
}
if (ans[ans.length - 1] === 0) {
ans.pop();
}
ans.reverse();
return ans.join("");
};Python решение
сопоставлено/оригиналclass Solution:
def multiply(self, num1: str, num2: str) -> str:
if num1 == "0" or num2 == "0":
return "0"
first_number = num1[::-1]
second_number = num2[::-1]
N = len(first_number) + len(second_number)
answer = [0] * N
for index, digit in enumerate(second_number):
answer = self.addStrings(
self.multiplyOneDigit(first_number, digit, index), answer
)
if answer[-1] == 0:
answer.pop()
answer.reverse()
return "".join(str(digit) for digit in answer)
def multiplyOneDigit(self, first_number: str, digit2: str, num_zeros: int):
currentResult = [0] * num_zeros
carry = 0
for digit1 in first_number:
multiplication = int(digit1) * int(digit2) + carry
carry = multiplication // 10
currentResult.append(multiplication % 10)
if carry != 0:
currentResult.append(carry)
return currentResult
def addStrings(self, result: list, answer: list) -> list:
carry = 0
new_answer = []
for digit1, digit2 in zip_longest(result, answer, fillvalue=0):
curr_sum = digit1 + digit2 + carry
carry = curr_sum // 10
new_answer.append(curr_sum % 10)
return new_answerGo решение
сопоставлено/оригиналfunc addStrings(num1 []int, num2 []int) []int {
ans := []int{}
carry := 0
for i := 0; i < len(num1) || i < len(num2) || carry != 0; i++ {
digit1, digit2 := 0, 0
if i < len(num1) {
digit1 = num1[i]
}
if i < len(num2) {
digit2 = num2[i]
}
sum := digit1 + digit2 + carry
carry = sum / 10
ans = append(ans, sum%10)
}
if carry != 0 {
ans = append(ans, carry)
}
return ans
}
func multiplyOneDigit(firstNumber string, secondNumberDigit rune, numZeros int) []int {
currentResult := make([]int, numZeros)
carry := 0
for i := 0; i < len(firstNumber); i++ {
firstNumberDigit := firstNumber[i] - '0'
multiplication := int(secondNumberDigit-'0')*int(firstNumberDigit) + carry
carry = multiplication / 10
currentResult = append(currentResult, multiplication%10)
}
if carry != 0 {
currentResult = append(currentResult, carry)
}
return currentResult
}
func multiply(num1 string, num2 string) string {
if num1 == "0" || num2 == "0" {
return "0"
}
firstNumber := reverseString(num1)
secondNumber := reverseString(num2)
N := len(firstNumber) + len(secondNumber)
ans := make([]int, N)
for i, digit := range secondNumber {
result := multiplyOneDigit(firstNumber, rune(digit), i)
ans = addStrings(result, ans)
}
if ans[len(ans)-1] == 0 {
ans = ans[:len(ans)-1]
}
var answer strings.Builder
for i := len(ans) - 1; i >= 0; i-- {
answer.WriteString(strconv.Itoa(ans[i]))
}
return answer.String()
}
func reverseString(s string) string {
runes := []rune(s)
for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
runes[i], runes[j] = runes[j], runes[i]
}
return string(runes)
}Algorithm
1️⃣
Переверните оба числа. Инициализируйте массив ans с (N+M) нулями. Для каждой цифры в secondNumber:
Инициализируйте переменную carry, первоначально равную 0.
Инициализируйте массив (currentResult), который начинается с некоторого количества нулей, основываясь на позиции цифры в secondNumber.
2️⃣
Для каждой цифры в firstNumber:
Умножьте цифру из secondNumber на цифру из firstNumber и добавьте предыдущий carry к умножению.
Возьмите остаток от деления умножения на 10, чтобы получить последнюю цифру.
Добавьте последнюю цифру в массив currentResult.
Разделите умножение на 10, чтобы получить новое значение для carry.
3️⃣
После итерации по каждой цифре в первом числе, если carry не равен нулю, добавьте carry в currentResult.
Добавьте currentResult к ans.
Если последняя цифра в ans равна нулю, перед тем как перевернуть ans, необходимо удалить ноль из ans. В противном случае в финальном ответе будет ведущий ноль.
Переверните ans и верните его.
😎
Вакансии для этой задачи
Показаны активные вакансии с пересечением по тегам задачи.
Активных вакансий пока нет.