给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

题目描述

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。

思路

通过观察，m位数 * n位数的结果最多是 (m + n)位，并且由于int类型数据的局限性，不能用普通乘法得到相应的结果，
所以可以考虑构建一个(m + n)位的string数组保存num1 和num2 每一位相乘的结果，并且考虑进位。

实现

#include <iostream>
#include <vector>
#include <string>
#include <sstream>

using namespace std;

string multiply(string num1, string num2) 
{
    string str1 = "0";
    
    if (num1.compare("0") == 0 || num2.compare("0") == 0)
    {

    }
    else
    {        
        int n = num1.size();
        int m = num2.size();

        vector<int> num(m + n);

        for (int i = m - 1; i >= 0; i--)
        {
            for (int j = n - 1; j >= 0; j--)
            {
                int temp = (num1[j] - '0') * (num2[i] - '0');
                num[i + j + 1] += temp;
            }            
        }

        //最后一位不需要进位，所以从倒数第二位开始
        for (int i = m + n - 2; i >= 0; i--)
        {
            num[i] += num[i + 1] / 10;
            num[i + 1] = num[i + 1] % 10;
        }

        if (num[0] == 0)
        {
            num.erase(num.begin());
        }

        stringstream ss;
        copy(num.begin(), num.end(), ostream_iterator<int>(ss, ""));
        str1 = ss.str();        
    }
    return str1;
}

int main()
{
    string st = multiply("123456789", "987654321");

    cout << st << endl;
	return 0;
}

结果