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


觉得内容还不错?打赏个钢镚鼓励鼓励!!👍

香蕉先生 安全套 避孕套 物理延时套 水润倍滑 成人情趣用品 物理延时10只装
¥9.80
番茄红素维生素E软胶囊增强免疫力喜倍力搭配片男性成人保健品 1瓶装60粒
¥46.00
成人本科学士学位英语统一考试星级词汇大冲关(第2版 乱序版)
¥18.09
喜宝莉 一次性加厚纯棉洗脸巾抽取式干湿两用母婴可用棉柔巾 单包60片
¥13.93
年年好1.2米丝绒布全背胶金字对联《贺岁呈祥》2023兔年不带福字
¥19.90
美加净轻香滋养手部身体乳护手霜 250ml 国际调香大师 告别干燥护手霜
¥45.50
富昌 虾皮200g 小虾米海米干 海产干货紫菜蛋花汤原材料 调味食材
¥24.90
五虎爪 婴儿口罩10枚3d立体婴童口罩宝宝一次性口罩新生幼儿透气防护专用0-6月到1岁半 款式随机 白色
¥26.80