字符串相乘

发表于 | 分类于 | 阅读次数：
本文字数： 2.7k | 阅读时长 ≈ 7 分钟

问题提出

#43 字符串相乘

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

示例 :

1
2
3
> 输入: num1 = "123", num2 = "456"
> 输出: "56088"
>

说明：

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

解题思路1

使用常规的竖式计算法：算其中一个数的每位数与另一个数相乘，再将结果进位相加即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
string multiply(string num1, string num2) {
    int len1 = num1.length(), len2 = num2.length();
    if (len1 == 0 || len2 == 0) return "";
    if (num1 == "0" || num2 == "0") return "0";

    string ret = "0";
    if (len1 > len2) {
        swap(num1, num2);
        swap(len1, len2);
    }
    string power = "";

    for (int i = len1 - 1; i >= 0; i--) {
        ret = add(ret, single_multiply(num1[i] - '0', num2) + power);
        power += '0';
    }
    return ret;
}

string add(string a, string b) {
    string ret;
    int bias = 0, i, j, sum;
    int len1 = a.length(), len2 = b.length();
    for (i = len1 - 1, j = len2 - 1; i >= 0 && j >= 0; i--, j--) {
        sum = a[i] + b[j] + bias - '0' * 2;
        bias = sum / 10;
        ret += sum % 10 + '0';
    }
    while (i >= 0) {
        sum = a[i--] + bias - '0';
        bias = sum / 10;
        ret += sum % 10 + '0';
    }
    while (j >= 0) {
        sum = b[j--] + bias - '0';
        bias = sum / 10;
        ret += sum % 10 + '0';
    }
    if (bias == 1) ret += bias + '0';
    reverse(ret.begin(), ret.end());
    return ret;
}

string single_multiply(int n, string a) {
    if (n == 0) return "0";
    string ret;
    int i, bias = 0, sum;
    for (i = a.length() - 1; i >= 0; i--) {
        sum = n * (a[i] - '0') + bias;
        bias = sum / 10;
        ret += sum % 10 + '0';
    }
    if (bias != 0) ret += bias + '0';
    reverse(ret.begin(), ret.end());
    return ret;
}

解题思路2

上面这种方法有很多重复计算，比如算一位数的乘法和多位数的加法的时候都有进位，而这些进位运算是可以合并的，这样不仅代码简洁，效率也更高。

可以申请一个数组保存未进位中间结果，把进位放在最后来做。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
string multiply(string num1, string num2) {
    string ret;
    int n1 = num1.size(), n2 = num2.size();
    int k = n1 + n2 - 2, carry = 0;
    vector<int> v(n1 + n2, 0);
    for (int i = 0; i < n1; ++i) {
        for (int j = 0; j < n2; ++j) {
            v[k - i - j] += (num1[i] - '0') * (num2[j] - '0');
        }
    }
    for (int i = 0; i < n1 + n2; ++i) {
        v[i] += carry;
        carry = v[i] / 10;
        v[i] %= 10;
    }
    int i = n1 + n2 - 1;
    while (v[i] == 0) --i;
    if (i < 0) return "0";
    while (i >= 0) ret.push_back(v[i--] + '0');
    return ret;
}