43.字符串相乘

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

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

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

说明：
num1 和 num2 的长度小于110。
num1 和 num2 只包含数字 0-9。
num1 和 num2 均不以零开头，除非是数字 0 本身。
不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。

思路
1、字符转转整数，整数相乘，乘完转字符转，这样做发现数太大的话会一出

class Solution {
public:
    string multiply(string num1, string num2) {
        if (num1 == "0" || num2 == "0") return "0";
        long int temp;
        string res;
        long long  IntRes = 0;
        long int IntNum1 = string2int(num1);
        long int IntNum2 = string2int(num2);
        IntRes = IntNum1 * IntNum2;
        res = int2string(IntRes);
        return res;
    }
    int string2int (string StrNum)
    {
        long int Intnum = 0;
        long int temp = 0;
        for (int i = 0; i < StrNum.size(); i++)
        {
            temp = (StrNum[i] - '0');
            Intnum = Intnum * 10 + temp;
        }
        return Intnum;
    }
    string int2string(long int nums)
    {
        string res;
        long int temp;
        
        while (nums > 0)
        {
            temp = nums % 10;
            nums /= 10;
            res = res + char(temp + '0');
        }
        int j = res.size() - 1;
        string tem = "";
        for (int i = 0; i < res.size(); i ++)
        {
            tem = tem + res[j];
            j--;
        }
        return tem;

    }
};

2、分别对每一位进行运算，每一次运算都要记录下来余数和进位的数，方便进行下次计算。str[i + j + 1]是num1[j]和num2[i]相乘计算的那一位。

class Solution2
{
public:
    string multiply(string num1, string num2)
    {
        if (num1 == "0" || num2 == "0") return "0";
        int size1 = num1.size(), size2 = num2.size();
        string str(size1 + size2, '0');
        for (int i = size2 - 1; i >= 0; --i)
        {   
            int  AddNum = 0, LostNum = 0;
            for (int j = size1 - 1; j >= 0; --j)
            {
                int Temp1 =(num2[i] - '0')  * (num1[j] - '0') + AddNum;
                AddNum = Temp1 / 10;
                Temp1 = Temp1 % 10;
                int Temp2 = str[i + j + 1] - '0' + LostNum + Temp1;//对上一次的进位和这次的余数进行相加
                str[i + j + 1] = Temp2 % 10 + '0';
                LostNum = Temp2 / 10;
            }
            str[i] += LostNum + AddNum;
        }
        if (str[0] == '0')
        {
            str = str.substr(1, str.size());
        }
        return str;
    }
};