05 August 2008
Given two non-negative integers
and 1
num1
represented as strings, return the product of 1
num2
and 1
num1
, also represented as a string.1
num2
Example 1:
1
2
Input: num1 = "2", num2 = "3"
Output: "6"
Example 2:
1
2
Input: num1 = "123", num2 = "456"
Output: "56088"
Note:
1
num1
and 1
num2
is < 110.1
num1
and 1
num2
contain only digits 1
0-9
.1
num1
and 1
num2
do not contain any leading zero, except the number 0 itself.两个字符串表示的数字,相乘后返回字符串表示的乘积(这样可以计算超大数相乘,不受int和long数值范围的约束),就用多位数的乘法过程,每位相乘然后错位相加,把错位相加的结果保存在一个一维数组中,然后每位上算进位,最后每位就变成一位,去掉首位的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
class Solution {
public String multiply(String num1, String num2) {
int m = num1.length(), n = num2.length();
// 二者的乘积最大长度为m + n,例如"5" * "7"
int[] positions = new int[m + n];
for (int i = m - 1; i >= 0; i--) {
for (int j = n - 1; j >= 0; j--) {
//这步乘积可能是一位数或两位数
int product = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
// 在array的基础上加上新得到乘积,找到相应的位置
// 第一个位置是十位,第二个位置存个位
int tens = i + j;
int ones = i + j + 1;
int sum = product + positions[ones]; // ones是上一次乘积可能存上的tens
positions[tens] += sum / 10;
positions[ones] = sum % 10;
}
}
StringBuilder sb = new StringBuilder();
for (int p : positions) {
// 两个条件一起表示没有乘以0
if (!(sb.length() == 0 && p == 0)) {
sb.append(p);
}
}
return sb.length() == 0 ? "0" : sb.toString();
}
}