Leetcode-43 划水记录06 大数乘法

发布时间：2020-12-14 04:30:39 所属栏目：大数据来源：网络整理

导读：给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。示例 1: 输入: num1 = "2",num2 = "3" 输出: "6" 示例 2: 输入: num1 = "123",num2 = "456" 输出: "56088" 说明： num1 和 num2 的长度小于110

给定两个以字符串形式表示的非负整数 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）或直接将输入转换为整数来处理。

我的实现方法是模拟两个数乘法的竖式计算，但是速度好像不怎么好

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<int,vector<int>> 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<iRest.size()-1;iXh++)
    {
        if (iRest[iXh] == ‘0‘)
        {
            zeroNums++;
        }
        else
            break;
    }
    iRest.erase(0,zeroNums);
    return iRest;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!