温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

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

发布时间:2020-07-28 12:40:14 来源:网络 阅读:314 作者:hzChan 栏目:编程语言
给定两个以字符串形式表示的非负整数 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;
}
向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI