给定两个以字符串形式表示的非负整数 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)或直接将输入转换为整数来处理。
我的实现方法是模拟两个数乘法的竖式计算,但是速度好像不怎么好
专注于为中小企业提供成都网站设计、网站制作服务,电脑端+手机端+微信端的三站合一,更高效的管理,为中小企业金州免费做网站提供优质的服务。我们立足成都,凝聚了一批互联网行业人才,有力地推动了近1000家企业的稳健成长,帮助中小企业通过网站建设实现规模扩充和转变。
string multiply(string num1, string num2) {
int len1 = (num1).size();
int len2 = (num2).size();
string pLong = len1>len2?num1:num2;
string pShor = len1<=len2?num1:num2;
map> iRes;
for (int iXhbl=pShor.size()-1;iXhbl>=0;iXhbl--)
{
int iCarry = 0;//进位控制
string iResult;
for (int iXhbl2=pLong.size()-1;iXhbl2>=0;iXhbl2--)
{
int iSum=0;
if (iCarry)
{
iSum += iCarry;
iCarry = 0;
}
iSum += (pLong[iXhbl2] - '0')*(pShor[iXhbl]-'0');
if (iSum >= 10)
iCarry = iSum/10;
iResult +=( iSum % 10)+'0';
int djw = (pShor.size()-1- iXhbl) + 1 + (pLong.size() - 1 - iXhbl2);
iRes[djw].push_back((iSum % 10));
}
if (iCarry)
{
int djw = (pShor.size() - 1 - iXhbl) + 1 + pLong.size();
iRes[djw].push_back((iCarry ));
iResult += iCarry + '0';
}
}
int iCarry = 0;
string iRest;
for (int iXhbl=1;iXhbl<=pLong.size()+pShor.size();iXhbl++)
{
if (iRes[iXhbl].size() > 0)
{
int iSum = 0;
for (int iXhbl2=0;iXhbl2< iRes[iXhbl].size();iXhbl2++)
{
iSum += iRes[iXhbl][iXhbl2];
}
if (iCarry)
{
iSum += iCarry;
iCarry = 0;
}
if (iSum >= 10)
iCarry = iSum / 10;
iRest = iRest + (char)((iSum % 10) + '0');
}
}
if (iCarry)
{
iRest = iRest + (char)((iCarry % 10) + '0');
}
std::reverse(iRest.begin(), iRest.end());
//去除多余的0
int zeroNums=0;
for (int iXh=0;iXh