Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
40 lines (37 sloc) 933 Bytes
problem:
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.
----------------------------------------------------------------
solution:
//用vector记录,模拟乘法。m位的正整数与n位正整数相乘得到的是m+n位
string multiply(string num1, string num2)
{
int l1 = num1.size();
int l2 = num2.size();
if(l1 <= 0 || l2 <= 0)
return "";
string result = "";
vector<int> n(l1 + l2, 0);
for(int i = 0; i < l1; i++)
{
int n1 = num1[l1 - i - 1] - '0';
int carry = 0;
for(int j = 0; j < l2; j++)
{
int n2 = num2[l2 - j - 1] - '0';
carry = n1 * n2 + carry + n[i + j];
n[i + j] = carry % 10;
carry = carry / 10;
}
n[i + l2] = carry;
}
int i = l1 + l2 - 1;
while(i > 0 && n[i] == 0)
i--;
while(i >= 0)
{
result.append(1, n[i] + '0');
i--;
}
return result;
}