每天一题LeetCode【第32天】

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 吧~