43. Multiply Strings.md

43. Multiply Strings

思路

题目要求实现大整数乘法。

思路一

最直观的思路，就是是我们小学学的两数相乘的方法。回忆一下小学求456x123的过程:

        456
      x 123
    -------
       1368  ->   1238 
       921.  ->   9210
    + 456..  ->  45600 
    ------------------
               = 56088

即分成两个大步：

1. 求123中每个数字3、2、1分别对456的乘积1368、921和456；
2. 将上面得到的乘积相加（注意合理插入一些0）得最终结果56088。

我们将上面这两步定义成两个函数digit_mul_reversed_bigNum和reversed_bigNum_add，具体定义见代码详细解释。

为了方便处理，将所有用string表示的大数做了翻转处理，即123 -> "321"。

若m和n分别代表两个大数的长度，则易知时间复杂度O(mn)，空间复杂度O(m+n)。

思路二

虽然思路一很好想，但是实现起来略显复杂，而且需要先对字符串进行翻转，因此时间效率比较低。有没有elegant一点的方法？

我们知道，位数分别为len1和len2的两整数相乘，结果的位数不会超过len1 + len2（例如99 x 999 < 100 x 1000 = 100000），所以一开始我们可以开一个大小为len1 + len2的数组来存放这个乘积。而且，对于num1和num2中的每一个数字，我们都知道这两个数字的积对应于前面数组的哪一位，例如num1=456，num2=123时，6和3相乘结果对应于最终乘积的最末位(同时有个进位)，5与3的相乘结果对应于最终结果的倒数第二位(也有个进位)，以此类推。所以我们有如下算法:

1. 首先开一个大小为len1 + len2的int型数组res_num并初始化为0；
2. 对num1和num2做一个双重循环从后向前(即i、j的初始值分别为len1-1、len2-1)遍历，当前位置的两个数字相乘的结果对应res_num中的位置是i+j+1（例如初始时i=len1-1，j=len2-1，对应的就是len1+len2-1），所以应该num_res[i + j + 1] += (num1[i] - '0') * (num2[j] - '0');
3. 处理进位，使num_res每一个元素都位于0到9，我们也可以在第2步同时处理进位，但是单独处理的话计算量会小一些。
4. 到目前位置我们就得到了数值型的结果，再转换成string即可，注意跳过前导0。

时间复杂度O(mn)，空间复杂度O(m+n)。

C++

思路一

class Solution {
private:
    string digit_mul_reversed_bigNum(const int &dt, const string &bN, int lead_0){
        /*第1步：求一个数字(0-9)与一个大数的乘积。
        bN: 翻转后的大数，例如bN="321"代表123
        lead_0: 结果中前面先插入的0的个数 
        return: 乘积(同样是翻转了的，即"0129"代表9210)
        */
        if(!dt) return "0";
        if(bN.size() == 1 && bN[0] == '0') return "0";
        string res;
        while(lead_0--) res += '0'; // 插入0
        int mul, cin = 0; // cin表示进位，下同
        for(int i = 0; i < bN.size(); i++){
            mul = dt * (bN[i] - '0') + cin;
            res += (mul % 10 + '0');
            cin = mul / 10;
        }
        if(cin > 0) res += (cin + '0');
        return res;
    }
    void reversed_bigNum_add(string &a, const string &b){ // a+=b
        /*第2步: 将第1步求得的乘积累加起来，a和b都是翻转后的大数
        注意 a 传入的是引用
        */
        int sum, cin = 0;
        int i = 0, len1 = a.size(), len2 = b.size();
        while(i < len1 && i < len2){ // 大数加法
            sum  = a[i] - '0' + b[i] - '0' + cin;
            a[i] = sum % 10 + '0';
            cin = sum / 10;
            i++;
        }
        // 下面两个while至多执行一个
        while(i < len1 && cin > 0){ // a 比 b 长
            sum = a[i] - '0' + cin;
            a[i] = sum % 10 + '0';
            cin = sum / 10;
            i++;
        }
        while(i < len2){ // b 比 a 长
            if(!cin){ // 如果cin=0，那么直接将b的剩余部分接到a后面即可
                a.append(b, i, len2);
                break;
            }
            sum = b[i] - '0' + cin;
            a += (sum % 10 + '0');
            cin = sum / 10;
            i++;
        }
        if(cin > 0) a += (cin + '0');
    }
public:
    string multiply(string num1, string num2) {
        reverse(num1.begin(), num1.end());
        reverse(num2.begin(), num2.end());
        string res, tmp;
        for(int i = 0; i < num1.size(); i++){
            tmp = digit_mul_reversed_bigNum(num1[i]-'0', num2, i);
            reversed_bigNum_add(res, tmp);
        }
        reverse(res.begin(), res.end());
        if(res.empty()) return "0";
        return res;
    }
};

思路二

class Solution {
public:
    string multiply(string num1, string num2) {
        int len1 = num1.size(), len2 = num2.size();
        string res;
        int num_res[len1 + len2] = {0};
        for(int i = len1 - 1; i >= 0; i--){
            for(int j = len2 - 1; j >= 0; j--){
                num_res[i + j + 1] += (num1[i] - '0') * (num2[j] - '0');
                // num_res[i + j + 1] += num_res[i + j + 2] / 10;
                // num_res[i + j + 2] %= 10;
            }
        }
        for(int i = len1 + len2 - 1; i > 0; i--){ // 处理进位
            num_res[i - 1] += num_res[i] / 10;
            num_res[i] %= 10;
        }
        
        int i = 0;
        while(i < len1 + len2 && !num_res[i]) i++; // 跳过前导0
        while(i < len1 + len2) res += num_res[i++] + '0';        
        if(res.empty()) return "0";
        return res;
    }
};