题目链接: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.
这道题的要求是计算大数乘法。其中大数是以字符串的形式表示,任意大,非负,返回结果以字符串形式。
这道题其实就是模拟整数乘法。
假设两个整数的长度分别为了l1和l2,则其最后结果长度为l1+l2(最后有进位)或者l1+l2-1(最后没有有进位)。
因此,可以先用长度为l1+l2的数组记录结果,最后再转成字符串。
进行乘法的时候,先把各个位的相乘结果对应累加起来,即第1个整数的第i位(低位到高位)和第2个整数的第j位(低位到高位)相乘的结果应该存放在数组的i+j位。然后再统一处理进位。
然后再统一处理进位。
最后再将数组转成字符串前,需要跳过前面的零。如果结果只有0,则只返回0。
时间复杂度:O(l1l2)(l1和l2分别为两个整数长度)
空间复杂度:O(l1+l2)
1 class Solution
2 {
3 public:
4 string multiply(string num1, string num2)
5 {
6 vector<int> vi(num1.size() + num2.size(), 0);
7 for(int i = 0; i < num1.size(); ++ i)
8 for(int j = 0; j < num2.size(); ++ j)
9 vi[i + j] += (num1[num1.size() - i - 1] - ‘0‘) * (num2[num2.size() - j- 1] - ‘0‘);
10
11 for(int i = 0, c = 0; i < vi.size(); ++ i)
12 {
13 int num = vi[i] + c;
14 vi[i] = num % 10;
15 c = num / 10;
16 }
17
18 string s = "";
19 int i = vi.size();
20 while(-- i >= 0 && vi[i] == 0);
21 if(i < 0)
22 s = "0";
23 else
24 for( ; i >= 0; -- i)
25 s += vi[i] + ‘0‘;
26
27 return s;
28 }
29 };