题目
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.
答案
class Solution {
public String multiply(String num1, String num2) {
num1 = (new StringBuilder(num1)).reverse().toString();
num2 = (new StringBuilder(num2)).reverse().toString();
int[] sum = new int[num1.length() + num2.length()];
for(int i = 0; i < num1.length(); i++) {
int numi = num1.charAt(i) - '0';
for(int j = 0; j < num2.length(); j++) {
sum[i + j] += numi * (num2.charAt(j) - '0');
}
}
StringBuilder sb = new StringBuilder();
for(int i = 0; i < sum.length; i++) {
int mod = sum[i] % 10;
int carry = sum[i] / 10;
if(i < sum.length - 1) sum[i + 1] += carry;
sb.insert(0, mod);
}
while(sb.charAt(0) == '0' && sb.length() > 1)
sb.deleteCharAt(0);
return sb.toString();
}
}
