【leetcode】43 Multiply Strings

发表于 | 分类于 ，

重载乘法


描述

给定两个个字符串 num1 和 num2, 求 num1 * num2

样例

样例1

1
2
输入: num1 = "2" num2 = "3"
输出: "6"

样例2

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

思路

写三个函数

  1. 计算两个字符串的乘积
  2. 计算两个字符串的和
  3. 计算一个字符串和一个单一的数字的结果

第一个函数调用第二个和第三个函数

也可以这样,result[i+j]

1
2
3
int temp = (result[i + j] - '0') + carry + ((num1[i] - '0')*(num2[j] - '0'));
result[i + j] = (temp % 10) + '0';
carry = (temp / 10);

代码

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
57
58
59
60
61
62
63
64
65
class Solution {
public:
    string multiply(string num1, string num2) {
        if( num1== "0" || num2 == "0" ) { return "0" ;}
        string result = "0";//保存结果

        // Use each number of num1 to calculate the string num2
        for(int i=num1.size()-1;i>=0;i--){
            string multOne = multiplyOne(num2,num1[i]-'0',num1.size()-1 -i);
            cout << "multOne\t" << multOne <<endl;
            result = add(result,multOne);
            cout << "add\t" << result <<endl;
        }

        return result;

    }

    // Add string num1 and num2;
    string add(string num1, string num2) {
        int carry = 0;
        string result ="";
        int i=num1.size()-1 ,j = num2.size()-1 ;
        while( i>=0 && j>=0){
            int tempAdd = num1[i]-'0' + num2[j] -'0';
            tempAdd += carry;
            carry = tempAdd / 10;
            result = to_string(tempAdd %10) +result;
            i--,j--;
        }

        while(j>=0){
            int temp = num2[j] -'0' + carry;
            carry = temp /10;
            result = to_string(temp%10) + result;
            j--;
        }

        while(i>=0){
            int temp = num1[i] -'0' + carry;
            carry = temp /10;
            result = to_string(temp%10) + result;
            i--;
        }
        if(carry){ result = to_string(carry) + result; }
        return result;
    }

    // Get result when calculate the string num and single intger n
    string multiplyOne(string num,int n,int count){
        int carry = 0;
        string result = "";
        for(int i= num.size()-1;i>=0;i--){
            int multiTemp = n * (num[i]-'0') + carry;
            carry = multiTemp /10;
            result = to_string(multiTemp%10)+result;
        }
        if(carry){ result = to_string(carry) + result; }
        while(count > 0) {
            result += "0";
            count--;
        }
        return result;
    }
};

另一种方法

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
class Solution {
public:
    string multiply(string num1, string num2) {
        string result(num1.size() + num2.size(),'0');
        // cout << result <<endl;
        reverse(begin(num1),end(num1));
        reverse(begin(num2),end(num2));

        int carry = 0;
        for(int i = 0; i < num1.size(); ++i){
            for(int j = 0; j < num2.size(); ++j){
                int temp = (result[i + j] - '0') + carry + ((num1[i] - '0')*(num2[j] - '0'));
                result[i + j] = (temp % 10) + '0';
                carry = (temp / 10);
            }

            if(carry){
                int temp = (result[i + num2.size()] - '0') + carry;
                result[i+ num2.size()] = (temp%10) + '0';
                carry = temp/10;
            }
        }

        if(carry){
            result[num1.size() + num2.size() - 1] += ((result[num1.size() + num2.size() - 1] - '0') + carry) + '0';
        }

        reverse(begin(result),end(result));
        int zi = 0;
        for(;zi != result.size() && result[zi] == '0'; zi++);
        if(zi == result.size()){
            return "0";
        }

        return result.substr(zi);
    }
};

参考

原题链接
两个string 相加