力扣算法题—043字符串相乘

解题思路：

/*
                  4   5     6
                * 1   2     3
            ——————————
                 12   15   18
             8   10      12
         4   5    6
    ————————————
    v _  _   _    _    _    _
    v 0  4   13   28   27   18
    进位处理即得答案
*/

 1 class Solution {
 2 public:
 3     string multiply(string num1, string num2) {
 4         int len1 = num1.length();
 5         int len2 = num2.length();
 6         vector<int>v(len1 + len2, 0); //用来存放乘积，最后的结果的位数不可能超过len1+len2
 7         
 8         for (int i = len1 - 1; i >= 0; i--) {
 9             for (int j = len2 - 1; j >= 0; j--) {
10                 v[i + j + 1] += (num1[i] - '0') * (num2[j] - '0');  //此处很巧妙，对应位乘完后相加，并始终不进位
11             }
12         }
13 
14         // 处理进位
15         int carry = 0;
16         for (int i = len1 + len2 - 1; i >= 0; i--) {
17             v[i] += carry;
18             carry = v[i] / 10;
19             v[i] %= 10;
20         }
21 
22         string re = "";
23         int flag = 1;
24         for (int i = 0; i < len1 + len2; ++i) {
25             if (v[i] == 0 && flag)continue;//去除前位是0的数
26             re += v[i] + '0';
27             flag = 0;
28         }
29         if (flag)
30             re += '0';//若全为0即得0
31         return re;
32     }
33 };
34 
35 
36 void T043() {
37     Solution s;
38     string num1;
39     string num2;
40     num1 = "2";
41     num2 = "3";
42     cout << s.multiply(num1, num2) << endl;
43     num1 = "123";
44     num2 = "456";
45     cout << s.multiply(num1, num2) << endl;
46     num1 = "0";
47     num2 = "456";
48     cout << s.multiply(num1, num2) << endl;
49 }