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.
思路
- 与手动算乘法思想一致，利用每一轮乘法可以利用上一次乘法的结果
int product = carry + result[i + j + 1] + (num1.charAt(i) - '0') * (num2.charAt(j) - '0'); - 需注意每一次外循环时，需要把carry清零
- 每一次内循环结束时，不要忘了最后一个carry
- 在去掉得到的String头部的0时，不要忘了处理答案是0的情况，
k < result.length - 1，需要保留最后一位。 - 为了不超时，必须先用while去掉头部的0，再用for loop得到答案
class Solution {
public String multiply(String num1, String num2) {
int len1 = num1.length();
int len2 = num2.length();
int len3 = len1 + len2;
int[] result = new int[len3];
int carry = 0;
int i = 0, j = 0;
for (i = len1 -1; i >= 0; i--) {
carry = 0;
for (j = len2 - 1; j >= 0; j--) {
int product = carry + result[i + j + 1] + (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
carry = product / 10;
result[i + j + 1] = product % 10;
}
result[i + j + 1] = carry;
}
StringBuilder resultStr = new StringBuilder();
int k = 0;
//k < result.length - 1 为了保证 结果是0这样的数，不能把这个0去掉
while (k < result.length - 1 && result[k] == 0) {
k++;
}
for (; k < result.length; k++) {
resultStr.append(String.valueOf(result[k]));
}
return resultStr.toString();
}
}
