NC10 大数乘法

描述

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

数据范围： 读入的数字大小满足 0≤n≤101000

要求：空间复杂度 O(m)，时间复杂度 O(m2)（假设m是n的长度）

示例1

输入：

"11","99"

返回值：

"1089"

说明：

11*99=1089 

示例2

输入：

"1","0"

返回值：

"0"

解题思路：

我们可以使用模拟的方法来计算两个数字的乘积。具体步骤如下：

1. 定义一个字符串result，用于存储计算结果，初始值为"0"。
2. 如果其中一个数字为0，则直接返回result。
3. 如果两个数字都不为0，则从低位到高位依次计算每一位的乘积，并将结果加到result中。
4. 最后返回result。

Java代码实现如下：

public String multiply(String num1, String num2) {
    int n1 = num1.length(), n2 = num2.length();
    int[] res = new int[n1 + n2];
    for (int i = n1 - 1; i >= 0; i--) {
        int n1i = num1.charAt(i) - '0';
        for (int j = n2 - 1; j >= 0; j--) {
            int n2j = num2.charAt(j) - '0';
            res[i + j + 1] += n1i * n2j;
        }
    }
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < res.length; i++) {
        int digit = res[i] % 10;
        int carry = res[i] / 10;
        res[i] = digit;
        if (i < res.length - 1) {
            res[i + 1] += carry;
        }
    }
    int i = res.length - 1;
    while (i >= 0 && res[i] == 0) {
        i--;
    }
    if (i == -1) {
        return "0";
    }
    sb.append(res[i]);
    for (i--; i >= 0; i--) {
        sb.append(res[i]);
    }
    return sb.toString();
}