[LeetCode] 大数问题，相加和相乘，题 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.

class Solution {

public:

    string multiply(string num1, string num2) {

    }

};

我的解法是每次提取num2的一位，然后和num1相乘，所得结果并入string res中，这样虽然每次都要新定义一个string，效率略低，但是思路比较清晰：把字符串相乘划分成了“字符串和数字相乘” 和 “字符串相加” 两个子问题，分别解决就可以。

处理时先将num1，和num2逆序，使得最低位在[0] 位置，这样处理起来比较方便，不易写错。

class Solution {

public:

    string multiply(string num1, string num2) {

        if(num1.length() ==  || num2.length() == )

            return "";

        if(num1.length() ==  && num1[] == '') return "";

        if(num2.length() ==  && num2[] == '') return "";

        string res(num1.length() + num2.length(), '');

        int i = , j = ;

        reverse(num1.begin(), num1.end());

        reverse(num2.begin(), num2.end());

        for(i = ; i < num2.length(); ++i){

            int offset = i;

            string tmp(offset + num1.length() + , '');

            int add = ;

            for(j = ; j < num1.length(); ++j){

                int tmpMul = (num1[j] - '') * (num2[i] - '') + add;

                add = tmpMul / ;

                tmp[j + offset] = (tmpMul % ) + '';

            }

            tmp[j + offset] = add + '';

            plus(res, tmp);

        }

        int countStartZero = ; //高位'0'的个数

        for(i = res.length() - ; i >=  && res[i] == ''; --i, ++countStartZero);

        if(countStartZero == res.length()) return "";

        res = res.substr(, res.length() - countStartZero);

        reverse(res.begin(), res.end());

        return res;

    }

private:

    void plus(string &s1, string &s2){

        int add = ;

        for(int i = ; i < s1.length() && (add >  || i < s2.length()); ++i){

            int tmp = (s1[i] - '') + add;

            if(i < s2.length()) tmp += (s2[i] - '');

            add = tmp / ;

            s1[i] = (tmp % ) + '';

        }

    }

};