字符串相乘

发表于 更新于 本文字数： 472 阅读时长 ≈ 2 分钟

43 字符串相乘

两数A位和B位，相加后位数最大为max(A, B)+1；相乘后最大位数为A+B

1.1 常规法

将两个串的指针位置m和n、进位c统一放入while循环，代码就会很优美。 代码可以继续优化速度存储：addtion函数改为原地相加，但是会破坏代码的逻辑性，就不改了。

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
class Solution {
public:
    string addtion(string& num1, string& num2){
        int m = num1.size()-1, n = num2.size()-1;
        int c = 0;
        string ret;
        while(m>=0 || n>=0 || c){
            int a = m>=0 ? num1[m]-'0' : 0; // 越界定0技巧
            int b = n>=0 ? num2[n]-'0' : 0; // 越界定0技巧
            int s = a + b + c;
            ret.push_back('0' + s % 10);
            c = s / 10;
            --m, --n;
        }
        reverse(ret.begin(), ret.end()); // 反转
        return ret;
    }
    
    string multiply(string num1, string num2) {
        if(num1=="0" || num2=="0") return "0";
        string res = "0";
        int cnt = 0; // 记录表示每次乘完左移的0的个数
        int m = num2.size()-1;
        while(m >= 0){
            int n = num1.size()-1;
            int b = num2[m] - '0';
            int c = 0;
            string ret(cnt, '0'); // 初始化"左移"0
            while(n>=0 || c){
                int a = n>=0 ? num1[n]-'0' : 0; // 越界定0技巧
                int s = a * b + c;
                ret.push_back('0' + s % 10);
                c = s / 10;
                --n;
            }
            reverse(ret.begin(), ret.end()); // 反转
            res = addtion(res, ret);
            --m, ++cnt;
        }
        return res;
    }
};

1.2 优化竖式 (LC高赞)(很难想到啊)

说明图
num1[i] x num2[j] 的结果为 tmp(位数为两位，”0x”,”xy”的形式)，其第一位位于 res[i+j]，第二位位于 res[i+j+1]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    string multiply(string num1, string num2) {
        if(num1 == "0" || num2 == "0") return "0";
        int m = num1.size(), n = num2.size();
        vector<int> temp(m+n, 0); // 数组哦
        for(int i=m-1; i>=0; --i){
            for(int j=n-1; j>=0; --j){
                int cur = (num1[i]-'0') * (num2[j]-'0') + temp[i+j+1];
                temp[i+j+1] = cur % 10; // 存储计算结果低位 =
                temp[i+j] += cur / 10; // 存储计算结果高位 +=
            }
        }
        string ret; ret.reserve(m+n);
        int i = 0;
        for(; i<temp.size(); ++i) // 去掉前缀0
            if(temp[i] != 0) break;
        for(; i<temp.size(); ++i) // 放入字符串
            ret.push_back(char(temp[i] + '0'));
        return ret;
    }
};