Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.
Note:You must not use any built-in BigInteger library or convert the inputs to integer directly.
Example 1:
Input:num1 = "2", num2 = "3"Output:"6"
Example 2:
Input:num1 = "123", num2 = "456"Output:"56088"
Constraints:
1 <= num1.length, num2.length <= 200
num1 and num2 consist of digits only.
Both num1 and num2do not contain any leading zero, except the number 0 itself.
class Solution {
public String multiply(String num1, String num2) {
// 两个长度为a, b的数字相乘, 结果程度不超过a+b. 比如99 * 99 < 100 * 100 = 10000
// 0,1,2依次是最高位,第二高位,第三高位,以此类推
// 比如 10400,对应的下标是
// 01234
// 这样的好处是转换位字符串的时候不需要再倒序一遍
char[] res = new char[num1.length() + num2.length()];
// 用'0'初始化结果数组
Arrays.fill(res, '0');
// 两个数字当前正在处理的位置, 位置0代表个位. 比如123, 第0位代表0
// 为了方便理解,就不用i和j来推算出pos了
int pos1 = -1;
for (int i = num1.length() - 1; i >= 0; i--) {
int d1 = num1.charAt(i) - '0';
// 每次循环表示处理第一个数的高一位
pos1++;
// 每次内层循环,第二个数从新从个位开始算起
int pos2 = -1;
for (int j = num2.length() - 1; j >= 0; j--) {
int d2 = num2.charAt(j) - '0';
pos2++;
// 个位数相乘, 结果不超过两位
int prod = d1 * d2;
// 假如个位跟十位相乘, 结果的个位要放在最终结果的十位, 即 pos1 + pos2 = 0 + 1 = 1
// 假如有10位, 现在要赋值给第0位, 则实际要操作的是第10位,即 10 - 0 = 10
// 举个例子, 12345, 现在要给十位加一,实际上要操作的下标是 4 - 1 = 3
res[res.length - 1 - (pos1 + pos2)] += prod % 10;
// System.out.printf("res[%d] += %d \n", res.length - 1 - (pos1 + pos2), prod % 10);
// 结果的十位要再往高一位累加
res[res.length - 1 - (pos1 + pos2 + 1)] += prod / 10;
// System.out.printf("res[%d] += %d \n", res.length - 1 - (pos1 + pos2 + 1), prod / 10);
// 进位先不管, 最后再统一处理
}
}
// 从十位开始统一往后处理进位; 最低为和最高位肯定没有进位, 所以不处理
for (int i = res.length - 2; i >= 1; i--) {
if (res[i] - '0' >= 10) {
res[i - 1] += (res[i] - '0') / 10;
res[i] = (char)(((res[i] - '0') % 10) + '0');
}
}
// 最后把前面的0除掉, 但是最后一位肯定是要保留的(全0的情况)
int left = 0;
for (; left < res.length - 1; left++) {
if (res[left] != '0') break;
}
// debug: 输出数组看看
// for (char c : res) System.out.println((int)(c - '0'));
// 比如00511, left=2, 实际长度位3, 即 res.length - left = 5 - 2 = 3
// 01234
return new String(res, left, res.length - left);
}
}
