[LeetCode]43.Multiply Strings

【题目】

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.

【分析】

高精度乘法（大数乘法）

其实更多地是考察乘法运算的本质。基本思路是和加法运算有一定的相似处，都是从低位到高位对每一位进行计算。只是进位和结果长度复杂一些。

我们仍然是从低位到高位对每一位进行计算，假设第一个数长度是n，第二个数长度是m，我们知道结果长度为m+n或者m+n-1（没有进位的情况）。

对于最终结果上的某一位i，要计算这个位上的数字，我们需要对所有能组合出这一位结果的位进行乘法，即第1位和第i位，第2位和第i-1位，... ，然后累加起来，

最后我们取个位上的数值，然后剩下的作为进位放到下一轮循环中。在这里我们每一组合时都要计算有没有产生进位，如果有放到下一位上，不用所有累加起来在计算。

时间复杂度是O(m*n) ?空间复杂度O(m+n)。

【代码】

/*********************************
*   日期：2015-01-28
*   作者：SJF0115
*   题目: 43.Multiply Strings
*   网址：https://oj.leetcode.com/problems/multiply-strings/
*   结果：AC
*   来源：LeetCode
*   博客：
**********************************/
#include <iostream>
#include <cstring>
using namespace std;

class Solution {
public:
    string multiply(string num1,string num2) {
        int len1 = num1.length();
        int len2 = num2.length();
        // 容错处理
        if(len1 <= 0 || len2 <= 0){
            return "";
        }//if
        int sum = 0;
        int len3 = len1 + len2;
        char result[len3];
        memset(result,'0',sizeof(result[0])*(len3+1));
        for(int i = len1 - 1,m = 0;i >= 0;--i,++m){
            for(int j = len2 - 1,n = 0;j >= 0;--j,++n){
                sum = (num1[i] - '0') * (num2[j] - '0') + result[m+n] - '0';
                result[m+n] = sum % 10 + '0';
                // 进位
                result[m+n+1] += sum / 10;
            }//for
        }//for
        //确定乘积的位数
        while(result[len3] == '0' && len3 > 0){
            --len3;
        }//while
        //注意：加''
        result[len3+1] = '';
        //翻转
        int temp;
        for(int i = 0,j = len3;i < j;++i,--j){
            temp = result[i];
            result[i] = result[j];
            result[j] = temp;
        }//for
        return string(result);
    }
};

int main(){
    Solution solution;
    string num1("0");
    string num2("123");
    string result = solution.multiply(num1,num2);
    // 输出
    cout<<result<<endl;
    return 0;
}

/*for(int i = 0;i < result.size();++i){
        for(int j = 0;j < result[i].size();++j){
            cout<<result[i][j]<<" ";
        }
        cout<<endl;
    }*/

【分析二】

[算法]Karatsuba快速相乘算法

【代码二】

class Solution {
public:
    string multiply(string num1,string num2) {
        int len = MakeSameLen(num1,num2);
        if(len == 0){
            return 0;
        }//if
        // all digit are one
        if(len == 1){
            return to_string((num1[0] - '0')*(num2[0] - '0'));
        }//if
        int mid = len / 2;
        // Find the first half and second half of first string.
        string x1 = num1.substr(0,mid);
        string x0 = num1.substr(mid,len - mid);
        // Find the first half and second half of second string
        string y1 = num2.substr(0,mid);
        string y0 = num2.substr(mid,len - mid);
        // Recursively computer
        string z0 = multiply(x0,y0);
        string z1 = multiply(AddString(x1,x0),AddString(y1,y0));
        string z2 = multiply(x1,y1);
        // (z2*10^(2*m))+((z1-z2-z0)*10^(m))+(z0)
        // z2*10^(2*m)
        string r1 = ShiftString(z2,2*(len - mid));
        // (z1-z2-z0)*10^(m)
        string r2 = ShiftString(MinusString(MinusString(z1,z2),z0),len - mid);
        return  AddString(AddString(r1,r2),z0);
    }
private:
    // given two unequal sized bit strings,converts them to
    // same length by adding leading 0s in the smaller string. Returns the
    // the new length
    int MakeSameLen(string& num1,string& num2){
        int len1 = num1.length();
        int len2 = num2.length();
        if(len1 < len2){
            for(int i = 0;i < len2 - len1;++i){
                num1 = "0" + num1;
            }//for
            return len2;
        }//if
        else{
            for(int i = 0;i < len1 - len2;++i){
                num2 = "0" + num2;
            }//for
            return len1;
        }//else
    }
    // big number minus function
    string MinusString(string num1,string num2) {
        int len1 = num1.length();
        int len2 = num2.length();
        // 相等
        if(num1 == num2){
            return "0";
        }//if
        // 正负
        bool positive = true;
        if(len1 < len2 || (len1 == len2 && num1 < num2)){
            positive = false;
            // 交换使之num1 > num2
            string tmp = num1;
            num1 = num2;
            num2 = tmp;
            int temp = len1;
            len1 = len2;
            len2 = temp;
        }//if
        string result;
        int i = len1 - 1,j = len2 - 1;
        int a,b,sum,carray = 0;
        // 从低位到高位对位做减法
        while(i >= 0 || j >= 0){
            a = i >= 0 ? num1[i] - '0' : 0;
            b = j >= 0 ? num2[j] - '0' : 0;
            sum = a - b + carray;
            carray = 0;
            // 不够减
            if(sum < 0){
                sum += 10;
                carray = -1;
            }//if
            result.insert(result.begin(),sum + '0');
            --i;
            --j;
        }//while
        // 删除前导0
        string::iterator it = result.begin();
        while(it != result.end() && *it == '0'){
            ++it;
        }//while
        result.erase(result.begin(),it);
        return positive ? result : "-"+result;
    }
    // big number add function
    string AddString(string num1,string num2){
        int len1 = num1.length();
        int len2 = num2.length();
        // 容错处理
        if(len1 <= 0){
            return num2;
        }//if
        if(len2 <= 0){
            return num1;
        }
        string result;
        int i = len1-1,j = len2-1;
        int a,carry = 0;
        // 倒序相加
        while(i >= 0 || j >= 0 || carry > 0){
            a = i >= 0 ? num1[i] - '0' : 0;
            b = j >= 0 ? num2[j] - '0' : 0;
            // 按位相加并加上进位
            sum = a + b + carry;
            // 进位
            carry = sum / 10;
            result.insert(result.begin(),sum % 10 + '0');
            --i;
            --j;
        }//while
        return result;
    }
    // 移位
    string ShiftString(string num,int len){
        if(num == "0"){
            return num;
        }//if
        for(int i = 0;i < len;++i){
            num += "0";
        }//for
        return num;
    }
};