首页 > 代码库 > 43. Multiply Strings

43. Multiply Strings

2024-09-03 15:42:45   242人阅读

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2.

Note:

  1. The length of both num1 and num2 is < 110.
  2. Both num1 and num2 contains only digits 0-9.
  3. Both num1 and num2 does not contain any leading zero.
  4. You must not use any built-in BigInteger library or convert the inputs to integer directly.

Subscribe to see which companies asked this question.

来源： https://leetcode.com/problems/multiply-strings/

分析

与大数相加类似
下面的算法是按照正常的算数过程，计算出num1和num2每个位数字的乘积，然后再相加
28ms
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
class Solution {
public:
    string multiply(string num1, string num2) {
        string result;
        for(int i = num2.size() - 1; i >=0; --i){
            string tmp = multi(num1, num2[i]-‘0‘);
            for(int j = num2.size() - i - 1; j > 0 && tmp !="0"; --j)tmp.push_back(‘0‘);
            result = add(result, tmp);
        }
        return result;
    }
     
    string multi(string s, int num){
        if(num == 0) return "0";
        int c = 0;
        string result;
        for(int i = s.size() - 1; i >= 0; --i){
            int all = (s[i]-‘0‘) * num + c;
            result.push_back(all%10 + ‘0‘);
            c = all/10;
        }
        if(c != 0)
            result.push_back(‘0‘+c);
        reverse(result.begin(), result.end());
        return result;
    }
     
    string add(string num1, string num2){
        string result, s1, s2;
        s1.assign(num1.rbegin(), num1.rend());
        s2.assign(num2.rbegin(), num2.rend());
        int a, b, c = 0, sum = 0;
        auto l1 = s1.begin(), l2 = s2.begin();
        while(l1 != s1.end() || l2 != s2.end()){
            l1 != s1.end() ? a = (*l1) - ‘0‘: a = 0;
            l2 != s2.end() ? b = (*l2) - ‘0‘: b = 0;
            sum = a + b + c;
            result.push_back(sum%10 + ‘0‘);
            c = sum / 10;
            if(l1 != s1.end()) l1++;
            if(l2 != s2.end()) l2++;
        }
        if(c != 0){
            result.push_back(c + ‘0‘);
        }
        reverse(result.begin(), result.end());
        return result;
    }
};

进一步改进
因为add函数每一次都要reverse两个string，最后算数结束还需要再次reverse结果，导致效率很低

其实可以将乘法和最后相加的过程整合在一起。
这里用到一个条件，两个数（一个n位，一个m位）相乘，则乘积最大长度，不超过n+m位
这样的话，建立一个n+m位的string，作为存储乘积结果的字符串result，每次每个数字相乘后，就和result相加

num1: "11223" n = 5
num2: "123456" m = 6
index:  0 1 2 3 4 5 6 7 8 9 10
result: 0 0 0 0 0 0 0 0 0 0 0 当 i = 2; j = 3时，指向的result位置是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
23
24
class Solution {
public:
    string multiply(string num1, string num2) {
        int n = num1.size(), m = num2.size();
        string result(n + m, ‘0‘);
        for(int i = n - 1; i >= 0; --i){
            int c = 0;
            for(int j = m - 1; j >= 0; --j){
                c = result[i + j + 1]-‘0‘ + (num1[i] - ‘0‘) * ( num2[j] - ‘0‘) + c;
                result[i + j + 1] = c % 10 + ‘0‘;
                c = c / 10;
            }
            //we can think that position j = -1, num2[j] == 0, then the result = result[i + j + 1] + c = result[i] + c;
            result[i] +=c;
        }
         
        size_t startpos = result.find_first_not_of("0");
        if (string::npos != startpos) {
            return result.substr(startpos);
        }
        return "0";
    }
     
};



null


43. Multiply Strings


联系
我们