这是我参与8月更文挑战的第10天，活动详情查看：8月更文挑战

前言

力扣第四十三题 字符串相乘 如下所示：

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

示例 1:

输入: num1 = "2", num2 = "3"
输出: "6"
复制代码

示例 2:

输入: num1 = "123", num2 = "456"
输出: "56088"
复制代码

一、思路

题目的意思还是比较简单的：将两个用 字符串表示的非负整数 的乘积用字符串表示

题目中明确规定了不可以使用 大数类型，所以不可以通过直接相乘得到结果了。那么既然要得到的是 乘积，我们不难想到使用 竖式 来模拟乘法。

两数相乘有以下两个规律（均不为零的情况）：

1. M 位和 N 位的结果相乘，乘积位数为 M+N 或 M+N-1（可能没有进位，如 999 x 10 = 9990，乘积为 4 位）
2. nums1[i] * nums2[j] 的结果为 XY。X 高位是乘积中下标为 [i+j] 的值，Y 低位是乘积中下标为 [i+j+1] 的值（字符串中靠左为高位）

tips：如下图所示，18 为 nums1[2] 和 nums[2] 的乘积。故低位 8 在乘积中的位置为 5，高位 1 在乘积中的位置为 4

所以我们可以根据规律很轻松的得出两者的乘积，再将乘积转为字符串即可。

举个例子

变量说明：
int[] ret：乘积结果数组

此处以实例2中的 num1 = "123", num2 = "456" 作为例子，具体的步骤如下所示：

1. i=2，j=2 时， nums1[2] * nums2[2] = 18，故 ret[5]=8, ret[4]=1。如下图所示：

2. i=2，j=1 时， nums1[2] * nums2[1] = 16（需要加上前面的进位），故 ret[4]=6, ret[3]=1。如下图所示：

3. i=2，j=0 时， nums1[2] * nums2[0] = 13（需要加上前面的进位），故 ret[3]=3, ret[2]=1。如下图所示：

4. ……，i=1 以及 i=0 时，步骤都是一样的，故省略。

5. 得到最终的结果：ret=[0, 5, 6, 0, 8, 8]

6. 故转换为字符串位 "56088"

二、实现

实现代码

实现代码与思路中保持一致

    public String multiply(String num1, String num2) {
        // 特殊情况处理
        if ("0".equals(num1) || "0".equals(num2)) {
            return "0";
        }
        int[] ret = new int[num1.length() + num2.length()];
        // 从低位向高位，即从右到左
        for (int i=num1.length()-1; i>-1; i--) {
            int n1 = (int)num1.charAt(i) - (int)('0');
            for (int j=num2.length()-1; j>-1; j--) {
                int n2 = (int)num2.charAt(j) - (int)('0');
                // 可能会发生进位
                int sum =  ret[i+j+1] + n1 * n2;
                // 低位
                ret[i + j + 1] = sum % 10;
                // 高位
                ret[i + j] += sum / 10;
            }
        }

        StringBuilder result = new StringBuilder();
        for (int i = 0; i < ret.length; i++) {
            // 防止
            if (i == 0 && ret[i] == 0) continue;
            result.append(ret[i]);
        }
        return result.toString();

    }
复制代码

测试代码

    public static void main(String[] args) {
        String ret = new Number43().multiply("123", "456");
        System.out.println(ret);
    }
复制代码

结果

三、总结

感谢看到最后，非常荣幸能够帮助到你~♥