Keshawn_lu's Blog

Leetcode 43. 字符串相乘

字数统计: 532阅读时长: 2 min
2020/08/13 Share

题目简介:

给定两个以字符串形式表示的非负整数 num1num2,返回 num1num2 的乘积,它们的乘积也表示为字符串形式。

示例 1:

1
2
输入: num1 = "2", num2 = "3"
输出: "6"

示例 2:

1
2
输入: num1 = "123", num2 = "456"
输出: "56088"

说明:

  1. num1num2 的长度小于110。
  2. num1num2 只包含数字 0-9
  3. num1num2 均不以零开头,除非是数字 0 本身。

思路:

模拟竖式乘法(小学数学的重要性2333),用位数少的字符串去乘位数多的字符串(即位数少的摆在下面)。

然后开始以下步骤:

  1. 从最后一位开始,将当前一位的乘法结果加起来,得到字符串sum
  2. 根据当前的位数将sum后补0,得到当前一位的最终结果字符串sum
  3. sum加到答案字符串中。

字符串相加时,可以根据 415. 字符串相加 的思路写一个函数。

tip:

  • 若字符串中有"0"字符串,直接返回"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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
class Solution {
public:

string add_string(string &res, string& temp){

int flag = 0;

string ans;

while(res.size() < temp.size())
res = '0' + res;

while(temp.size() < res.size())
temp = '0' + temp;


for(int i = res.size() - 1; i >= 0; i--){

int sum = res[i] - '0' + temp[i] - '0';

if(flag == 1){

sum++;
flag = 0;
}

if(sum >= 10){

flag = 1;
sum -= 10;
}

ans = to_string(sum) + ans;
}

if(flag == 1)
ans = '1' + ans;

return ans;
}

string multiply(string num1, string num2) {

string res;

if(num1 == "0" || num2 == "0")
return "0";

//用位数少的去乘位数多的
if(num1.size() > num2.size()){

string temp = num1;
num1 = num2;
num2 = temp;
}

for(int i = num1.size() - 1; i >= 0; i--){

string sum;
int count = 0;
for(int j = num2.size() - 1; j >= 0; j--){

int now_mul = (num1[i] - '0') * (num2[j] - '0');

if(count > 0){

now_mul += count;
count = 0;
}

if(now_mul >= 10){

count = now_mul / 10;
now_mul = now_mul % 10;
}

sum = to_string(now_mul) + sum;
}

if(count > 0)
sum = to_string(count) + sum;

for(int k = 0; k < num1.size() - i - 1; k++){

sum = sum + '0';
}

res = add_string(res, sum);
}

return res;
}
};
CATALOG
  1. 1. 题目简介:
  2. 2. 思路:
  3. 3. 代码如下: