题目描述

以字符串的形式读入两个数字，编写一个函数计算它们的乘积，以字符串形式返回。

（字符串长度不大于10000，保证字符串仅由'0'~'9'这10种字符组成）

方法一： 模拟

解题思路

用代码模拟2个数相乘的过程即可。整体的流程就是：把 num2 从右往左遍历，每一个数字和 num1 进行相乘， 最后把每次相乘的结果相加就得到答案。

需要注意的是每次相乘的时候，因为有可能数字非常大，超出了整型、长整型的表示范围，所以每次相乘的时候仍然需要用 字符串的形式保存结果，把每次相乘的结果相加，仍然也是 2 个字符串相加。

在写代码的过程中，注意下进位的问题及反转的问题就可以。

这里以 12 * 99 为例， 大体流程思路如下图所示：

复杂度分析

时间复杂度： O(N * M + M * max(N, M))，N 为 num1 的长度， M 为 num2 的长度。

需要遍历 num2 的每个数字，每个数字还需要和 num2 的每个数字进行相乘，所以这里复杂度为 O(N*M)。

在每次相乘结果相加的时候，也仍然需要遍历每个数字进行相加，这里遍历的次数就看 num1 和 num2 哪个字符串更长，即时间复杂度为 O(max(N, M))。
而整个过程在外面大的循环里，即 num2 的遍历循环里，所以这里复杂度为 O(M*max(N, M))。

所以，最后总的时间复杂度为 O(N * M + M * max(N, M))

空间复杂度： O(N + M)，N 为 num1 的长度， M 为 num2 的长度。

num1 和 num2 相乘的结果的最长长度为 N + M , 最长不会超过它，所以空间复杂度为 O(N + M)

示例代码

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param num1 string字符串 第一个整数
     * @param num2 string字符串 第二个整数
     * @return string字符串
     */
    public String solve (String num1, String num2) {
        // 判断不合法的输入
        if (num1 == null || num1.length() == 0 || num2 == null || num2.length() == 0) {
            return null;
        }
        // 如果 num1 或 num2 其中有一个为 0， 则最后相乘的结果为 0
        if ("0".equals(num1) || "0".equals(num2)) {
            return "0";
        }

        char[] chars1 = num1.toCharArray();
        char[] chars2 = num2.toCharArray();
        // 最后的结果
        String res = "0";
        // 相乘之后，后面需要补零的个数
        int zero = 0;
        // 从右往左遍历 num2 字符串中的每一个数字， 使其和 num1 字符串相乘， 再相加，即得最后结果
        for (int i = chars2.length - 1; i >= 0; i--) {
            // 每一个数字和 num1 字符串相乘的结果
            StringBuilder temp = new StringBuilder();
            // 保存进位
            int carry = 0;

            // 将后面需要的零补齐
            for (int j = 0; j < zero; j++) {
                temp.append('0');
            }
            zero++;

            // 取出 num2 字符串的每一个数字， 记为 y
            int y = chars2[i] - '0';
            // 使 y 和 num1 字符串相乘
            for (int j = chars1.length - 1; j >= 0; j--) {
                int x = chars1[j] - '0';
                int num = x * y + carry;
                temp.append(num % 10);
                carry = num / 10;
            }
            // 如果最后进位不为 0 ， 则还需要往前进 carry 位
            if (carry != 0) {
                temp.append(carry);
            }
            // 把每次相乘的结果相加起来，就是最后的结果
            res = bigNumberAdd(res, temp.reverse().toString());
        }
        return res;
    }

    /**
     * 
     * @param num1 第一个数字字符串
     * @param num2 第二个数字字符串
     * @return  两个字符串相加之后的结果
     */
    public String bigNumberAdd(String num1, String num2) {
        // 判断不合法输入
        if (num1 == null || num1.length() == 0 || num2 == null || num2.length() == 0) {
            return null;
        }
        // num1 字符串的下标， 从右往左遍历
        int index1 = num1.length() - 1;
        // num2 字符串的下标， 从右往左遍历
        int index2 = num2.length() - 1;

        // 最后相加的结果
        StringBuilder res = new StringBuilder();
        // 保存进位
        int carry = 0;

        // num1 或 num2 只要有一个字符串还有值，就继续循环
        while (index1 >= 0 || index2 >= 0) {
            // 拿到 num1 的一个数字
            int x = index1 >= 0 ? num1.charAt(index1--) - '0' : 0;
            // 拿到 num2 的一个数字
            int y = index2 >= 0 ? num2.charAt(index2--) - '0' : 0;
            // 拿到的 2 个数字相加，要考虑进位的情况
            int num = x + y + carry;
            // 该位只保存个位数
            res.append(num % 10);
            // 十位数要往前进一位
            carry = num / 10;
        }
        // 如果最后进位不为 0 ， 则还需要往前进 carry 位
        if (carry != 0) {
            res.append(carry);
        }
        return res.reverse().toString();
    }
}

方法二： 优化方法一

解题思路

方法一就是平常我们做乘法的步骤，先相乘，再相加。

优化之后就是直接算乘法，把 num1 的每一位数字 和 num2 的每一位数字相乘， 相乘的结果放到对应的位置上，最后我们再处理相乘之后的结果即可。

如果 num1 的长度为 N ， num2 的长度为 M， 则 num1 * num2 的结果最长长度为 N + M，所以开辟一个长度为 N + M 的整型数组来操作相乘的结果。

但有时候长度没有达到 N+M ， 所以这里需要判断一下有没有前置零的影响，这块具体思路请参照代码。

这里以 12 * 99 为例， 大体流程如下图所示：

得到了 num 数组，之后的操作就是每个位置只保留一位数字，即处理进位：

复杂度分析

时间复杂度： O(N*M)，N 为 num1 的长度， M 为 num2 的长度。

代码里有 2 层嵌套的 for 循环， 就是把 num1 的每一个数字 和 num2 的每一个数字相乘的消耗。

空间复杂度：O(N+M)，N 为 num1 的长度， M 为 num2 的长度。

需要开辟一个长度为 N + M 的整型数组来操作相乘之后的结果。

示例代码

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param num1 string字符串 第一个整数
     * @param num2 string字符串 第二个整数
     * @return string字符串
     */
    public String solve(String num1, String num2) {
        // 判断不合法的输入
        if (num1 == null || num1.length() == 0 || num2 == null || num2.length() == 0) {
            return null;
        }
        // 如果有一个字符串为 0 ，结果就是 0 
        if ("0".equals(num1) || "0".equals(num2)) {
            return "0";
        }

        // 最后相乘的结果，长度最多就是 2 个字符串的长度相加
        int[] num = new int[num1.length() + num2.length()];

        // num1 的每一个数字， 和 num2 的每一个数字相乘；  放到 num 数组的对应位置上
        for (int i = num1.length() - 1; i >= 0; i--) {
            for (int j = num2.length() - 1; j >= 0; j--) {
                // 同一个位置可能有多种情况映射过来， 所以结果位置上的结果取个累加和即可
                num[i + j + 1] += (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
            }
        }
        // 如果最后的结果有进位，那么 num 数组的第一位数不为零； 
        // 如果没进位，则为零。这种情况需要注意不要这个零。
        int end = num[0] == 0 ? 1 : 0;
        StringBuilder res = new StringBuilder();
        // 保存进位的值
        int carry = 0;
        // 从后往前遍历 num 数组，最后的结果有进位则遍历到 0 结束，没进位就遍历到 1 结束。
        for (int i = num.length - 1; i >= end; i--) {
            // 数组上对应位置的数 和 进位相加的结果
            int temp = num[i] + carry;
            // temp的个位数，才是属于对应位置上的数
            res.append(temp % 10);
            // temp的十位数，是属于对应位置的前一个位置上的数，即是进位的值
            carry = temp / 10;
        }
        // 最后的进位不为零，也是计算的结果，往前进 carry 位即可。
        if (carry != 0) {
            res.append(carry);
        }

        // 根据上述的流程，把 res 倒序一下，就是最后 2 个字符串相乘的结果
        return res.reverse().toString();
    }

}