【Multiply Strings】cpp

题目：

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) {

            const int n1 = num1.size(), n2 = num2.size();

            if ( num1=="" || num2=="") return "";

            vector<char> ret;

            for ( int i=n1-; i>=; --i )

            {

                vector<char> local(,'');

                int v = , carry = , curr = ;

                for ( int j=n2-; j>=; --j )

                {

                    v= (num1[i]-'')*(num2[j]-'');

                    carry = v/;

                    curr = v%;

                    carry += ((local[]-'')+curr)/;

                    curr = ((local[]-'')+curr)%;

                    local[] = curr+'';

                    local.insert(local.begin(), carry+'');

                }

                if (local[]=='') local.erase(local.begin());

                // cout << string(local.begin(),local.end()) << endl;

                // add zeros

                for ( int z=n1-; z>i; --z) local.push_back('');

                // cout << string(local.begin(),local.end()) << endl;

                carry = , curr = ;

                for ( int r=ret.size()-, l=local.size()-; r>= || l>=; --r,--l )

                {

                    if ( r>= && l>= )

                    {

                        curr = (carry+(ret[r]-'')+(local[l]-''))%;

                        carry = (carry+(ret[r]-'')+(local[l]-''))/;

                        local[l] = curr+'';

                    }

                    else

                    {

                        curr = (carry+(local[l]-''))%;

                        carry = (carry+(local[l]-''))/;

                        local[l] = curr+'';

                    }

                }

                if (carry!=) { local.insert(local.begin(), carry+''); }

                ret = local;

            }

            return string(ret.begin(),ret.end());

    }

};

tips：

就是一些字符串操作的细节，考虑进位，0这类的细节。

======================================

第二次过这道题，憋了好久。主要是有个思维误区，认为tmp比ret最多多一位；但是，比如52*4这样的例子，2*4=8 50*4=200就不止一位了。

解决了这个误区，代码AC了。

class Solution {

public:

    string multiply(string num1, string num2) {

            if ( num1=="" || num2=="" ) return "";

            vector<char> ret(num2.size(),'');

            for ( int i=num1.size()-; i>=; --i )

            {

                // mupltiply ret

                vector<int> tmp;

                int val = , carry = ;

                for ( int j=num2.size()-; j>=; --j )

                {

                    val = (num2[j]-'')*(num1[i]-'')+carry;

                    tmp.insert(tmp.begin(), val%);

                    carry = val/;

                }

                if ( carry> ) tmp.insert(tmp.begin(), carry);

                for ( int k=; k<num1.size()--i; ++k ) tmp.push_back();

                // merge tmp & ret

                while ( tmp.size()>ret.size() ) ret.insert(ret.begin(),'');

                val = ;

                carry = ;

                for ( int m=tmp.size()-; m>=; --m )

                {

                    val = (ret[m]-'') + tmp[m] + carry;

                    ret[m] = val%+'';

                    carry = val/;

                }

                if ( carry> ) ret.insert(ret.begin(), carry+'');

            }

            return string(ret.begin(), ret.end());

    }

};

巴特西

【Multiply Strings】cpp

最新文章

热门文章