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] + 进位;


代码

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
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次时间:

1
2
3
4
5
char * str1 = "9999999999999999999999999999999999999999999999999999";
char * str2 = "9999999999999999999999999999999999999999999999999999";
int i = 0;
for( i = 0 ; i <10000 ; i++)
multiply(str1, str2);

1
2
3
real	0m0.455s
user 0m0.451s
sys 0m0.003s

LeetCode 测试结果:
Leetcode结果

欣赏此文? 求鼓励,求支持!