LeetCode 43.Multiply Strings (字符串相乘)

绝地灬酷狼 2022-05-11 04:14 126阅读 0赞

题目描述：

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

示例：

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

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

**说明：**

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

Accepted C++ Solution:

class Solution {
    public:
        string multiply(string num1, string num2) {
            string sum(num1.size() + num2.size(), '0');
        
            for (int i = num1.size() - 1; 0 <= i; --i) {
                int carry = 0;
                for (int j = num2.size() - 1; 0 <= j; --j) {
                    int tmp = (sum[i + j + 1] - '0') + (num1[i] - '0') * (num2[j] - '0') + carry;
                    sum[i + j + 1] = tmp % 10 + '0';
                    carry = tmp / 10;    //进位
                }
                sum[i] += carry;    //加入最后的进位
            }
        
            size_t startpos = sum.find_first_not_of("0");
            if (string::npos != startpos) {             //代表sum中第一个不为0的字符存在
                return sum.substr(startpos);            //返回从startpos开始的子串
            }
            return "0";
        }
    };

使用两个嵌套的for循环，从每个输入数字的末尾开始反向工作。

我们预先分配我们的结果并在那里累积我们的部分结果。需要注意的一个特殊情况是，当我们的进位需要我们写入for循环之外的sum字符串时。

最后，我们修剪所有前导零，或者如果我们只计算零，则返回0。