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
找規(guī)律
這道題目也蠻有意思的吮廉。仔細想來，乘法是怎么做的呢汹族？
其實對兩個數(shù)做乘法，實際上就是將兩個數(shù)的位置兩兩組合做乘法，然后求和祝钢。對于num1的i位冷冗，和num2的j位，由于是兩個一位數(shù)相乘锁蠕，所以乘積一定在兩位數(shù)之內(nèi)夷野，所擺放到的位置就是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();
}
}
