[算法题]大数乘法

题目链接: 大数乘法

解题思路: 先做无进位乘法, 将对应无进位的乘积累加起来, 最后做进位即可.

图示:

首先可以定义一个存储无进位乘积的累加和的数组, 一开始会对乘数进行逆序处理, 所以下标位置如图所示, 每个乘数的每位对应的乘积存放在数组中的乘数的各位的下标相加处, 比如 1 和 5 相乘的乘积累加到其对应下标 2 + 1 = 3 处:

最后再进行进位处理并将结果逆序回来即可, 需要注意在逆序回来前注意前导 0 的问题, 比如:

100 * 0 = 000

如果不处理会输出 3 个 0, 题解代码如下:

class Solution 
{
public:
    string solve(string s, string t) 
    {
        //先逆序
        reverse(s.begin(), s.end());
        reverse(t.begin(), t.end());

        vector<int> arr(s.size() + t.size() - 1);//存储无进位乘法累加和的数组

        //进行无进位乘法 -- 每个值累加在arr[s下标+t下标]
        for(int i = 0; i < s.size(); ++i)
        {
            for(int j = 0; j < t.size(); ++j)
            {
                arr[i + j] += (s[i] - '0') * (t[j] - '0');
            }
        }

        string res; //记录结果
        int add = 0; //记录进位
        //再进行进位
        for(int i = 0; i < arr.size(); ++i)
        {
            add += arr[i];
            res += (add % 10) + '0';
            add /= 10;
        }
        //处理剩于进位
        if(add)
        {
            res += add + '0';
        }

        //处理前导零
        for(int i = res.size() - 1; i >= 1; i--)
        {
            if(res.back() == '0')
            {
                res.pop_back();
            }
        }

        reverse(res.begin(), res.end()); //在逆序回来
        return res;
    }
};