给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
**注意：**不能使用任何内置的 BigInteger 库或直接将输入转换为整数。
示例 1:
输入: num1 = "2", num2 = "3"
输出: "6"示例 2:
输入: num1 = "123", num2 = "456"
输出: "56088"提示：
1 <= num1.length, num2.length <= 200num1和num2只能由数字组成。num1和num2都不包含任何前导零，除了数字0本身。
解题思路：模拟 + 优化
对于相乘，如果我们是使用小学时候教的那种比如说 123 * 456，那么先拿 456 * 3 得到一个字符串，合并到结果字符串 ret 中，然后拿 456 * 2 得到一个字符串添加到结果字符串 ret 中，以此类推，其实这种方式是不太好搞的，因为这道题它给的是字符串，并且顺序是正序，我们在实际操作的时候就可能会有前导零啊，边界的情况，所以这种模拟方式需要优化一下！
我们可以每次拿 6 * 3、6 * 2、6 * 1，分别得到的就是 18、12、6，然后再拿 456 的第二位与 123 的每一位去相乘得到一个结果，最后再将这些结果进行累加放到数组中去，如下图所示：
接下来我们需要处理的就只是对这个结果集数组进行进位处理，也是很简单，最后就能得到结果！
不过我们其实可以一步到位，这里要利用一个结论，就是两个数相乘的最大位数不会超过两个数的位数相加！所以利用这个结论，我们可以用一个字符串 ret，开辟 num1.size() + num2.size() 大小，然后将其都初始化为 0。
然后在处理相乘的每一个结果的时候，该位置对应在字符串 ret 中的位置就是 ret[i + j + 1]，然后顺便该位置的结果求其进位，累加到其前面的位置也就是 ret[i + j]，这样子就同时完成了相乘和进位的操作！
要注意的是在操作过程中，我们是对字符串的操作，所以需要注意操作的字符是 '0'，而不是数字 0，它们的大小是不一样的！
最后还要注意的就是有可能整个结果字符串的位数是小于 num1.size() + num2.size() 的，也就是说有前导零，所以返回结果的时候要将前导零去掉！
class Solution {
public:
string multiply(string num1, string num2) {
if(num1 == "0" || num2 == "0")
return "0";
int n = num1.size() + num2.size();
string ret(n, '0'); // 创建一个两个字符串长度总和的字符串，然后初始化为'0'
for(int i = num1.size() - 1; i >= 0; --i)
{
for(int j = num2.size() - 1; j >= 0; --j)
{
int sum = (num1[i] - '0') * (num2[j] - '0') + (ret[i + j + 1] - '0'); // 先求出当前位置总和
ret[i + j + 1] = (sum % 10) + '0'; // 处理当前位置
ret[i + j] += sum / 10; // 处理进位
}
}
// 找到第一个非零元素
int i = 0;
while(i < n && ret[i] == '0')
i++;
return ret.substr(i);
}
};