题解 | 大数乘法

解法1：模拟

我们可以模拟两个整数相乘的过程。两个整数相乘的过程其实就是一个数与另一个数的每一位分别相乘，最后将每一位乘的结果加起来即可。例如：12*23 = 276，我们可以先用12*3 + 12*20结果依旧是276.所以我们可以将这个模拟过程实现出来。

1.依次取出一个数的每一位，与另一个数相乘。但要注意的是，与每一位相乘时要注意其倍数，而不能只乘该位对应的数字。但倍数只会影响结果后的0的个数，所以我们只需要给与每一个相乘的结果后面加上对应个数的0即可。solve和_solve实现的功能

2.我们得到每一位的结果之后，需要相加，而这其实就是大数相加。逆序遍历，模拟竖式相加即可。addTwoString实现的功能

class Solution
{
public:
    string _solve(string s, int multiplier, string multiple)// 被乘数，乘数，倍数
    {
        string ret;
        int carry = 0;
        for (int i = s.size() - 1; i >= 0 || carry; --i)
        {
            int x = i >= 0 ? s[i] - '0' : 0;
            carry += x * multiplier;
            ret += to_string(carry % 10);
            carry /= 10;
        }
        reverse(ret.begin(), ret.end());

        return ret + multiple; // 补零
    }

    string addTwoString(string s, string t)
    {
        if (!s.size() || !t.size())
            return !s.size() ? t : s;

        int i = s.size() - 1, j = t.size() - 1, carry = 0;
        string ret;
        while (i >= 0 || j >= 0 || carry)
        {
            carry += i < s.size() ? s[i--] - '0' : 0;
            carry += j < t.size() ? t[j--] - '0' : 0;
            ret += to_string(carry % 10);
            carry /= 10;
        }
        reverse(ret.begin(), ret.end());
        return ret;
    }

    string solve(string s, string t)
    {
        if (s[0] == '0' || t[0] == '0')
            return "0";

        // 依次取出s的每一位 与 t相乘
        string multiple; // 倍数，与个位乘是不补零，十位补一个......
        int tmp = 0;
        string ret;
        for (int i = s.size() - 1; i >= 0; --i)
        {
            tmp = (s[i] - '0'); // 取出每一位
            ret = addTwoString(ret, _solve(t, tmp, multiple));
            multiple += '0'; //下一个是十位，提前补零
        }
        return ret;
    }
};

解法2：无进位相乘

做法就是我们直接模拟竖式相乘，但是不管进位，直接存储下来，且对应位置的还应该加在一起，最后统一处理进位，让每个位置只保留一个数。下面模拟一个示例：

根据示例，我们需要存储下对应位置的乘积的和，而且这些乘积的位置是由规律的，逆序相乘，下标从0开始，那么两个数乘积的位置就在i+j处。所以我们创建一个vector用来存储对应位置的乘积的和，最后在对vector里面的数进行进位处理。进位处理时同时要考虑carry!=0的情况。

因为我们是逆序进行操作的，vector里面也是逆序存储的，按照上面的例子来说应该是72 87 21，所以最后还需要进行逆序。但是逆序前还得进行一步——处理前导零。因为我们开的vector空间比较大，但是存储时可能存储不完，就可能导致后面多余了0，我们需要将这些0给删除掉，之后再进行逆置。

class Solution 
{
public:
    string solve(string s, string t) 
    {
        if(s[0] == '0' || t[0] == '0')
            return "0";

        // 1.逆置后无进位相乘相加
        reverse(s.begin(), s.end());
        reverse(t.begin(), t.end());

        int n = s.size() , m = t.size();
        vector<int> add_no_carry(n+m);
        for(int i=0; i<n; ++i)
        {
            for(int j=0; j<m; ++j)
            {
                add_no_carry[i+j] += (s[i] - '0') * (t[j] - '0');        
            }
        }

        // 2.处理进位
        string ret;
        int carry = 0;
        for(auto e : add_no_carry)
        {
            carry += e;
            ret += carry % 10 + '0';
            carry /= 10;
        }

        // 数组处理完后，carry有可能还需要处理进位
        while(carry)
        {
            ret += carry % 10 + '0';
            carry /= 10;
        }

        // 3.处理前导零
        if(ret.back() == '0') ret.pop_back();
        reverse(ret.begin(), ret.end());

        return ret;
    }
};