T43. Multiply Strings【Medium】
题目
给出两个非负的整数 num1 和 num2 （都用字符串的形式表示），返回两者的乘积。
注意：
- num1 和 num2 的长度 <110
- num1 和 num2 只包含数字 0-9
- num1 和 num2 不能零打头
- 不能用任何的 BigInteger 的库，也不能直接把输入转化为 Integer
思路
这题难点在于长度可能达到100度，那就很非常长了，超出了 Int，long 这些类型的处理范围了。而且题目规定不能用 BigInteger 这类的库，所以是要自己实现。
做这题可以先用草稿纸写几个乘法运算找找规律。
例如：
1 2 3 <- 看右边的式子，可以看出来每位加减只要考虑自己的位置
* 3 2 以及进位就好了。
------- 同时可以看出， -
2 4 6 成绩所在位置 i = 两个乘数所在位置之和 - 1
+ 3 6 9 例如 2*2 两个 2 位置是 2，1，乘积 4 的位置=2+1-1=2
----------
3 9 3 6
剩下就看代码和注释吧~写了挺多注释！
代码
代码取自 Top Solution，稍作注释
public String multiply(String num1, String num2) {
//得到数字长度
int len1 = num1.length();
int len2 = num2.length();
//初始化用于保存乘积的数组,最长len1+len2,最短len1+len2-1
int[] product = new int[len1 + len2];
for (int i = len1 - 1; i >= 0; i--) {
for (int j = len2 - 1; j >= 0; j--) {
int index = len1 + len2 - i - j - 2;
//把字符转化为对应的数字(ASCII码相减, -'0'是转化的常用方法)相乘与之前的相加
product[index] += (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
//处理进位,如果连续进位,等下个循环会处理的,只管当前进位就好
product[index + 1] += product[index] / 10;
//获得该位置应有的数
product[index] %= 10;
}
}
//用StringBuilder 来创建返回的String
StringBuilder stringBuilder = new StringBuilder();
for (int i = product.length - 1; i > 0; i--) {
System.out.println(product[i]);
//去掉最高位是0的情况
if (stringBuilder.length() == 0&&product[i] == 0)
continue;
stringBuilder.append(product[i]);
}
//如果放在循环里面，当答案为0时则会被当成最高位的0去掉返回""
stringBuilder.append(product[0]);
return stringBuilder.toString();
}
补充
① 代码里 num1.charAt(i) - '0' 是干什么用的？
答：因为得到的字符进行运算的时候是以 ASCII 码对应的数字来运算的，'0' ~ '9' 对应 48 ~ 57 ,所以通常用 -'0' 来得到真正对应的数字。
② StringBuilder
.append()方法是将字符添加到缓冲区的末端。然后构成我们要输出的String。
其他的就不多说了，问 google 吧~
