题目

给定两个以字符串形式表示的非负整数  num1 和  num2，返回  num1 和  num2 的乘积，它们的乘积也表示为字符串形式。

示例 1:

输入: num1 = "2", num2 = "3"
输出: "6"

示例 2:

输入: num1 = "123", num2 = "456"
输出: "56088"

说明：

  1. num1 和 num2 的长度小于110。
  2. num1 和 num2 只包含数字 0-9。
  3. num1 和 num2 均不以零开头，除非是数字 0 本身。
  4. 不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

示例 1:

输入: num1 = "2", num2 = "3"
输出: "6"

示例 2:

输入: num1 = "123", num2 = "456"
输出: "56088"

说明：

  1. num1 和 num2 的长度小于110。
  2. num1 和 num2 只包含数字 0-9。
  3. num1 和 num2 均不以零开头，除非是数字 0 本身。
  4. 不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。

思路

模仿竖式乘法嘛

代码

class Solution {
public:
    string multiply(string num1, string num2) {
        if (num2[0] == '0' || num1[0] == '0') return "0";
        int m = num1.size(), n = num2.size();
        int res[m + n + 1] = {0};
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                res[i + j + 1] += (num1[m - i - 1] - '0') * (num2[n - j - 1] - '0');
            }
            res[0] = max(i + n, res[0]);
            for (int i = 1; i <= res[0]; i++) {
                if (res[i] < 10) continue;
                res[i + 1] += res[i] / 10;
                res[i] %= 10;
                if (i == res[0]) ++res[0];
            }
        }
        string ans(res[0], '0');
        for (int i = res[0]; i >= 1; i--) ans[res[0] - i] += res[i];
        return ans;
    }
};
执行用时 : 4 ms, 在所有 C++ 提交中击败了 99.25% 的用户

总结

  1. 竖式乘法，nums[i] * nums[j] ⇒ res[i + j ] 位置上
  2. 这里用res[0]代表位数，所以会ｒｅｓ相关的都加了１
  3. <mark>输入的数到底低位是代表位数高还是位数低位，就是注意一下大小端。</mark>