首页 > 其他 > 详细

LeetCode:Multiply Strings

时间:2014-05-19 14:10:03      阅读:389      评论:0      收藏:0      [点我收藏+]

题目链接

Given two numbers represented as strings, return multiplication of the numbers as a string.

Note: The numbers can be arbitrarily large and are non-negative

大整数乘法


我们以289*785为例

bubuko.com,布布扣

 

首先我们把每一位相乘,得到一个没有进位的临时结果,如图中中间的一行红色数字就是临时结果,然后把临时结果从低位起依次进位。对于一个m位整数乘以n位整数的结果,最多只有m+n位。         本文地址

注意:结果中需要去掉前导0,还需要注意结果为0的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    string multiply(string num1, string num2) {
        int n1 = num1.size(), n2 = num2.size();
        vector<int> tmpres(n1+n2, 0);
        int k = n1 + n2 - 2;
        for(int i = 0; i < n1; i++)
            for(int j = 0; j < n2; j++)
                tmpres[k-i-j] += (num1[i]-‘0‘)*(num2[j]-‘0‘);
        int carryBit = 0;
        for(int i = 0; i < n1+n2; i++)//处理进位
        {
            tmpres[i] += carryBit;
            carryBit = tmpres[i] / 10;
            tmpres[i] %= 10;
        }
        int i = k+1;
        while(tmpres[i] == 0)i--;//去掉乘积的前导0
        if(i < 0)return "0"; //注意乘积为0的特殊情况
        string res;
        for(; i >= 0; i--)
            res.push_back(tmpres[i] + ‘0‘);
        return res;
    }
};

 

上述算法的复杂度为O(n^2)(假设整数长度为n)

另外更高效的计算大整数乘法一般有:(1)karatsuba算法,复杂度为3nlog3≈3n1.585,可以参考百度百科面试题——大整数乘法乘法算法-Karatsuba算法。(2)基于FFT(快速傅里叶变换)的算法,复杂度为o(nlogn), 可以参考FFT, 卷积, 多项式乘法, 大整数乘法

 

【版权声明】转载请注明出处:http://www.cnblogs.com/TenosDoIt/p/3735309.html

LeetCode:Multiply Strings,布布扣,bubuko.com

LeetCode:Multiply Strings

原文:http://www.cnblogs.com/TenosDoIt/p/3735309.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!