leetcode刷题（68）——43. 字符串相乘

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

示例 1:

输入: num1 = “2”, num2 = “3” 输出: “6” 示例 2:

输入: num1 = “123”, num2 = “456” 输出: “56088” 说明：

num1 和 num2 的长度小于110。 num1 和 num2 只包含数字 0-9。 num1 和 num2 均不以零开头，除非是数字 0 本身。 不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。

需要注意的是，num1 和 num2 可以非常长，所以不可以把他们直接转成整型然后运算，唯一的思路就是模仿我们手算乘法。

比如说我们手算 123 × 45，应该会这样计算：

在这里插入图片描述

计算 123 × 5，再计算 123 × 4，最后错一位相加。这个流程恐怕小学生都可以熟练完成，但是你是否能把这个运算过程进一步机械化，写成一套算法指令让没有任何智商的计算机来执行呢？

你看这个简单过程，其中涉及乘法进位，涉及错位相加，还涉及加法进位；而且还有一些不易察觉的问题，比如说两位数乘以两位数，结果可能是四位数，也可能是三位数，你怎么想出一个标准化的处理方式？这就是算法的魅力，如果没有计算机思维，简单的问题可能都没办法自动化处理。

首先，我们这种手算方式还是太「高级」了，我们要再「低级」一点，123 × 5 和 123 × 4 的过程还可以进一步分解，最后再相加：

在这里插入图片描述

现在 123 并不大，如果是个很大的数字的话，是无法直接计算乘积的。我们可以用一个数组在底下接收相加结果：

在这里插入图片描述

![在这里插入图片描述](https://img-blog.csdnimg.cn/20200508113621127.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTIxMjQ0Mzg=,size_16,color_FFFFFF,t_70整个计算过程大概是这样，有两个指针 i，j 在 num1 和 num2 上游走，计算乘积，同时将乘积叠加到 res 的正确位置：

在这里插入图片描述

现在还有一个关键问题，如何将乘积叠加到 res 的正确位置，或者说，如何通过 i，j 计算 res 的对应索引呢？

其实，细心观察之后就发现，num1[i] 和 num2[j] 的乘积对应的就是 res[i+j] 和 res[i+j+1] 这两个位置。

在这里插入图片描述

明白了这一点，就可以用代码模仿出这个计算过程了：

class Solution {
    public String multiply(String num1, String num2) {
        int length1 = num1.length();
        int length2 = num2.length();
        int[] res = new int[length1+length2];
        //从个位数开始相乘
        for(int i=length1-1;i>=0;i--){
            for(int j=length2-1;j>=0;j--){
                int count1 = num1.charAt(i) - '0';
                int count2 = num2.charAt(j) - '0';
                int p1 = i+j;
                int p2 = i+j+1;
                int sum = count1*count2+res[p2];
                res[p2] = sum%10;
                res[p1] += sum/10;
            }
        }
        int i=0;
        while(i<res.length&&res[i]==0){
            i++;
        }
        String str="";
        for(;i<res.length;i++){
            str = str+(res[i]+"");
        }
        return str.length()==0?"0":str;
    }
}