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的情况下要进位,最后输出结果即可。

支付宝搜索:344355 领取随机红包

如果文章对您有帮助,欢迎给作者打赏