0%

[Leetcode]43. Multiply Strings(C++)

题目描述

题目链接: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

  1. The length of both num1 and num2 is < 110.
  2. Both num1 and num2 contain only digits 0-9.
  3. Both num1 and num2 do not contain any leading zero, except the number 0 itself.
  4. You must not use any built-in BigInteger library or convert the inputs to integer directly.

解题思路

一个比较容易想到的思路是模拟我们进行多位乘法的过程中,主要需要两个函数:一个函数用于求一个多位数和一个一位数的乘积;一个函数用于求两个整数的和。通过模拟求乘法过程即可,注意在将不同位的乘积相加时注意高位的和需要根据位数添加相应
0 的个数,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#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