Description
Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2.
Note:
The length of both num1 and num2 is < 110.
Both num1 and num2 contains only digits 0-9.
Both num1 and num2 does not contain any leading zero.
You must not use any built-in BigInteger library or convert the inputs to integer directly.
Solution
找规律
这道题目也蛮有意思的。仔细想来，乘法是怎么做的呢？
其实对两个数做乘法，实际上就是将两个数的位置两两组合做乘法，然后求和。对于num1的i位，和num2的j位，由于是两个一位数相乘，所以乘积一定在两位数之内，所摆放到的位置就是i + j和i + j + 1这两个位置上。
要注意对于carry的处理。p1和p2都可能会有carry哦。
class Solution {
public String multiply(String num1, String num2) {
int m = num1.length();
int n = num2.length();
int[] pos = new int[m + n];
for (int i = m - 1; i >= 0; --i) {
for (int j = n - 1; j >= 0; --j) {
int p1 = i + j;
int p2 = i + j + 1;
int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0') + pos[p2];
pos[p1] += mul / 10;
pos[p2] = mul % 10;
}
}
StringBuilder res = new StringBuilder();
for (int p : pos) {
if (res.length() == 0 && p == 0) {
continue;
}
res.append(p);
}
return res.length() == 0 ? "0" : res.toString();
}
}
