题目描述
题目链接:43. Multiply Strings
Given two non-negative integers num1
and num2
represented as strings, return the product of num1
and num2
, also represented as a string.
例子
例子 1
Input: num1 = “2”, num2 = “3” Output: “6”
例子 2
Input: num1 = “123”, num2 = “456” Output: “56088”
Note
- The length of both
num1
andnum2
is < 110.- Both
num1
andnum2
contain only digits0-9
.- Both
num1
andnum2
do not contain any leading zero, except the number 0 itself.- You must not use any built-in BigInteger library or convert the inputs to integer directly.
解题思路
一个比较容易想到的思路是模拟我们进行多位乘法的过程中,主要需要两个函数:一个函数用于求一个多位数和一个一位数的乘积;一个函数用于求两个整数的和。通过模拟求乘法过程即可,注意在将不同位的乘积相加时注意高位的和需要根据位数添加相应
0
的个数,代码如下:
#include <algorithm>
#include <string>
#include <vector>
class Solution {
public:
std::string multiply(std::string num1, std::string num2) {
if (num1 == "0" || num2 == "0") return "0";
std::vector<std::string> prods;
for (int i = num1.length() - 1; i >= 0; i--) {
std::string prod = multiplyOneDigit(num2, num1[i] - '0');
prod += std::string(num1.length() - 1 - i, '0');
prods.push_back(prod);
}
std::string result = prods[0];
for (int i = 1; i < prods.size(); i++) {
result = addTwoInt(result, prods[i]);
}
return result;
}
private:
std::string multiplyOneDigit(const std::string& num, int digit) {
std::string result = "";
int res = 0;
for (int i = num.length() - 1; i >= 0; i--) {
int prod = (num[i] - '0') * digit;
std::string prod_s =
std::to_string(prod) + std::string(num.length() - 1 - i, '0');
result = addTwoInt(result, prod_s);
}
if (res > 0) {
result += ('0' + res);
}
return result;
}
std::string addTwoInt(const std::string& num1, const std::string& num2) {
std::string result = "";
int ptr1 = num1.length() - 1, ptr2 = num2.length() - 1;
int res = 0;
while (ptr1 >= 0 || ptr2 >= 0) {
int sum = 0;
if (ptr2 >= 0) {
sum += num2[ptr2] - '0';
}
if (ptr1 >= 0) {
sum += num1[ptr1] - '0';
}
sum += res;
res = 0;
if (sum >= 10) {
res = 1;
sum -= 10;
}
ptr1--;
ptr2--;
result += ('0' + sum);
}
if (res > 0) {
result += ('0' + res);
}
std::reverse(result.begin(), result.end());
return result;
}
};
- 时间复杂度: O(mn)
- 空间复杂度: O(mn)
GitHub 代码同步地址: 43.MultiplyStrings.cpp
其他题目: GitHub: Leetcode-C++-Solution 博客: Leetcode-Solutions