43. 字符串相乘

>> 饿了么、美团外卖红包领取地址<<

题目：https://leetcode-cn.com/problems/multiply-strings/

代码：

class Solution {

    public String multiply(String num1, String num2) {
        //因为num1和num2最长为110，所以他们的乘积最大为110*2，预留110*2个数组空间
        int[] res = new int[110*2];

        //遍历第一个数
        for (int i = 0; i < num1.length(); i++) {
            //k的作用充当res结果的游标
            int k = i;
            int n1 = charToInt(num1.charAt(num1.length() - i - 1));
            //遍历第二个数
            for (int j = 0; j < num2.length(); j++) {
                int n2 = charToInt(num2.charAt(num2.length() - j - 1));
                //n1*n2的结果加到k位置的值上
                res[k] = res[k] + (n1 * n2);
                //因为会存在进位的情况，所以k+1位置的值要加上k位置的十位值，加完之后k位置的值要修正为k位置的个位值
                res[k + 1] = res[k + 1]+res[k] / 10;
                res[k] = res[k] % 10;
                k++;
            }
        }

        //因为算出来的res数组的结果是逆序的，且包含一堆0开头，所以这里是反转显示结果
        StringBuilder sb = new StringBuilder();
        boolean tag = false;
        for (int i = res.length - 1; i >= 0; i--) {
            if (tag || res[i] != 0) {
                sb.append(res[i]);
                tag = true;
            }
        }

        return sb.length()==0?"0":sb.toString();
    }

    /**
     * char类型转int值
     * @param c
     * @return
     */
    private int charToInt(char c) {
        return c - '0';
    }

}

解题思路：

因为题目要求不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理（要不然这个题目也没啥意义了）。所以我一开始考虑的是自己实现解析函数，即将字符串解析成int类型（自己实现Integer.parseInt()方法）然后直接两个int值相乘得到结果。但是提交代码之后发现，int类型长度不够，改成long也不够，因为num1和num2的长度最长可以为110，这啥类型肯定都不够长的。

没办法，只能自己实现乘法，采用的当然是从小就开始学的竖式，原理图如下：

具体的操作参考代码及注释，原理基本就是把数字拆开，2个数2个数相乘（九九乘法表），使用一个int数组来保存每次相乘的结果，需要考虑大于10的情况下要进位，最后输出结果即可。