非负大整数相乘

题目链接：https://leetcode-cn.com/problems/multiply-strings/

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

注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。

示例 1:

输入: num1 = "2", num2 = "3" 输出: "6" 示例 2:

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

提示：

1 <= num1.length, num2.length <= 200 num1 和 num2 只能由数字组成。 num1 和 num2 都不包含任何前导零，除了数字0本身。

思路：

普通的模拟，会用到大整数相加的模拟，慢

可以想下面这样，每次乘只算一位乘一位，这样就可以保证数字比较小，直接用int就能处理。

代码：

#include"stdafx.h"
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>
#include<map>
using namespace std;

class Solution {
public:
    string multiply(string num1, string num2) {
        int* a = (int*)malloc(sizeof(int) * (num1.size() + num2.size()));
        memset(a, 0, sizeof(int)*(num1.size() + num2.size()));
        for (int i = num1.size() - 1; i >= 0; i--)
        {
            for (int j = num2.size() - 1; j >= 0; j--)
            {
                int n1 = num1[i] - '0', n2 = num2[j] - '0';
                a[i + j + 1] += n1 * n2;
                a[i + j] += a[i + j + 1] / 10;
                a[i + j + 1] %= 10;
            }
        }
        string ans = "";
        for (int i = 0; i != num1.size() + num2.size(); i++)
        {
            if (ans == "" && a[i] == 0)continue;
            int t = a[i];
            ans += (t + '0');
        }
        if (ans == "")ans = "0";
        free(a);
        return ans;
    }
};

int main()
{
    string num1 = "2";
    string num2 = "3";
    Solution s;
    string ans = s.multiply(num1, num2);
    cout << ans << endl;
    return 0;
}