leetcode 43.字符串相乘

⭐️ 题目描述

---

🌟 leetcode链接：字符串相乘

思路：

---

代码：

class Solution {
public:
    string multiply(string num1, string num2) {
        
        if (num1 == "0" || num2 == "0") {
            return "0";
        }
        /*
            0  1  2 下标
            1  2  3
           *4  5  6
            6  12 18
          5 10 15
      0 4 8 12
      0 4 13 28 27 18   从后向前依次进一位
      0 5  6  0  8  8        
        */

        // 999 * 999 = 998,001 相乘计算 3位数 * 3位数 = 6位数 乘出来的结果是两个数的位数最大
        // 是两个位数长度相加 3 + 3

        vector<int> v(num1.size() + num2.size());   // 行数组

        for (int i = num1.size() - 1; i >= 0; i--) {
            for (int j = num2.size() - 1; j >= 0; j--) {
                // i + j + 1 下标位置是相乘后存在对应的下标位置
                v[i + j + 1] += (num1[i] - '0') * (num2[j] - '0');
            }
        }

        // 从后向前依次进一位
        for (int i = v.size() - 1; i > 0; i--) {
            v[i - 1] += v[i] / 10;
            v[i] %= 10;
        }

        string ans;
        int start_index = v.front() == 0 ? 1 : 0;
        while (start_index < v.size()) {
            ans += v[start_index] + '0';
            start_index++;
        }

        return ans;
    }
};
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

---