【leetcode】Multiply Strings

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.

各个位相乘，保存在数组中，最后再处理进位。

如

123*456

4,5,6

8,10,12

12,15,18

________________

4,13,28,27,18

即56088

 1 class Solution {
 2 public:
 3     string multiply(string num1, string num2) {
 4        
 5         if(num1=="0"||num2=="0") return "0";
 6        
 7         while(num1[0]=='0') num1.erase(0);
 8         while(num2[0]=='0') num2.erase(0);
 9        
10         int n1=num1.size();
11         int n2=num2.size();
12        
13         int *numArr1=new int[n1];
14         int *numArr2=new int[n2];
15        
16         int *result=new int[n1+n2];
17         memset(result,0,sizeof(int)*(n1+n2));
18         for(int i=0;i<n1;i++) numArr1[i]=num1[i]-'0';
19         for(int i=0;i<n2;i++) numArr2[i]=num2[i]-'0';
20        
21         for(int i=0;i<n1;i++)
22         {
23             for(int j=0;j<n2;j++)
24             {
25                 result[i+j+1]+=numArr1[i]*numArr2[j];
26             }
27         }
28        
29         int carry=0;
30         for(int i=n1+n2-1;i>=0;i--)
31         {
32             result[i]+=carry;
33             if(result[i]>=10)
34             {
35                 carry=result[i]/10;
36                 result[i]=result[i]%10;
37             }
38             else
39             {
40                 carry=0;
41             }
42         }
43        
44         string resultStr;
45         int k=0;
46         while(result[k]==0) k++;
47        
48         for(int i=k;i<n1+n2;i++)
49         {
50             resultStr.push_back(result[i]+'0');
51         }
52        
53         return resultStr;
54     }
55 };