字符串乘法

题目描述：

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

解法：

模拟竖式

竖式计算

使用两个指针i,j在num1和num2上游走，num1[i]和num2[j]的计算结果会放在[i+j]和[i+j+1]上

代码：

string multiply(string num1, string num2) {

    int m = num1.size(), n = num2.size();

    // 结果最多为 m + n 位数

    vector<int> res(m + n, 0);

    // 从个位数开始逐位相乘

    for (int i = m - 1; i >= 0; i--)

        for (int j = n - 1; j >= 0; j--) {

            int mul = (num1[i]-'0') * (num2[j]-'0');

            // 乘积在 res 对应的索引位置

            int p1 = i + j, p2 = i + j + 1;

            // 叠加到 res 上

            int sum = mul + res[p2];

            res[p2] = sum % 10;

            res[p1] += sum / 10;

        }

    // 结果前缀可能存的 0（未使用的位）

    int i = 0;

    while (i < res.size() && res[i] == 0)

        i++;

    // 将计算结果转化成字符串

    string str;

    for (; i < res.size(); i++)

        str.push_back('0' + res[i]);

    return str.size() == 0 ? "0" : str;

}