leetcode 43 | 字符串相乘
给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
示例 1:
输入: num1 = "2", num2 = "3"
输出: "6"示例 2:
输入: num1 = "123", num2 = "456"
输出: "56088"说明：
1.num1和num2的长度小于110。2.num1和num2只包含数字0-9。3.num1和num2均不以零开头，除非是数字 0 本身。- 4.不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。
分析：由于num1和num2的长度小于110，所以不能利用int，long等整型数据的*运算，因为肯定会超出其所能表示的范围。既然不能将其转为整数相乘，让我们可以怎么做呢？对了，我们可以用小学时学的乘法运算竖式来计算，你是否还记得呢~不记得也没事，看下面的示意图你就懂了~
比如我们要算78*4567，我们需要将78的个位依次乘以4567的个位，十位，百位和千位，分别得到56,48,40,32。然后再将7依次乘以其个位，十位，百位和千位，注意需要向左一个位置，然后再将相应位置的数进行相加，该进位的进行进位，最后得到结果356226。
既然我们我们已经理清了解题思路，那你还需要了解一个数学知识，那就是m位数乘以n位数，结果最多为m+n位数。了解了这些，我们就可以按照这种思路来编程实现了~
代码实现
class Solution {
public:
string multiply(string num1, string num2) {
int allLen = num1.size() + num2.size();
vector<int> tmpresult(allLen, 0);
string result(allLen, '0');
//模拟手算从最后一位开始处理
for (int i = num1.size() - 1; i >= 0; i--)
for (int j = num2.size() - 1; j >= 0; j--)
tmpresult[i + j + 1] += (num1[i] - '0')*(num2[j] - '0');
//进位
for (int i = allLen - 1; i>0; i--)
{
if (tmpresult[i]>9)
{
tmpresult[i - 1] += tmpresult[i] / 10;
tmpresult[i] %= 10;
}
}
//转换成字符串
for (int i = allLen - 1; i >= 0; i--)
result[i] = tmpresult[i] + '0';
if (result.find_first_not_of('0') == string::npos)
return "0";//排除全0的情况
return result.substr(result.find_first_not_of('0'), string::npos);
}
};本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2018-12-04，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
