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.

Note:

• The length of both num1 and num2 is < 110.
• Both num1 and num2 contain only digits 0-9.
• Both num1 and num2 do not contain any leading zero, except the number 0 itself.
• You must not use any built-in BigInteger library or convert the inputs to integer directly.

思路:

（Ps: 手写稍微忍耐一些吧 ^_^）

我们发现: p[i+j] = a[i] * b[j] + 进位;

代码

char* multiply(char* num1, char* num2) 
{
    int sz1 = strlen(num1);
    int sz2 = strlen(num2);
    int i, j = 0;
    int k = 0;
    int high, low;
    char *p = malloc(sizeof(char) * (sz1 + sz2 + 1));
    memset(p + sz1 + sz2, 0, 1);
    memset(p, '0', sz1 + sz2);

    for(i = 0; i < sz1; i++)
    {
        for(j =0; j < sz2; j++)
        {
           high = ( num1[i] - '0' )  * ( num2[j] - '0' ) / 10 + ( p[i+j] - '0');
           low = ( num1[i] - '0' )  * ( num2[j] - '0' )  % 10 + ( p[i+j+1] - '0');
        
           if(high > 9)
           {
                p[i+j] = high - 10 + '0';
                for(k = i+j-1; ; k--)
                {
                    if( p[k] != '9' )
                    {
                        p[k] += 1;
                        break;
                    }
                    else
                        p[k] = '0';
                }
           }
           else
                p[i+j] = high + '0';
        
           if(low > 9)
           {
                p[i+j+1]  = low - 10 + '0';
                for(k = i+j; ; k--)
                {
                    if( p[k] != '9' )
                    {
                        p[k] += 1;
                        break;
                    }
                    else
                        p[k] = '0';
                }
           }
           else
                p[i+j+1] = low + '0'; 
        }
    }
    
    for(i =0 ; i < (sz1 + sz2 - 1); i++, p++)
       if( *p != '0')
           return p; 

    return p;
}

LeetÇode-问题描述

运行1W次时间:

char * str1 = "9999999999999999999999999999999999999999999999999999";
char * str2 = "9999999999999999999999999999999999999999999999999999";
int i = 0;
for( i = 0 ; i <10000 ; i++)
    multiply(str1, str2);

real	0m0.455s
user	0m0.451s
sys		0m0.003s

LeetCode 测试结果: