43-字符串相乘

LeetCode 43. Multiply Strings

LeetCode-43

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

Note: You must not use any built-in BigInteger library or convert the inputs to integer directly.

Example 1:

Input: num1 = "2", num2 = "3"
Output: "6"

Example 2:

Input: num1 = "123", num2 = "456"
Output: "56088"

method: 模拟高精乘法

因为从后往前计算结果，前面有前导零不好删除，所以计算结果用逆序存储，后面再倒过来

从最低位开始从后往前计算，先把结果放到数组里，因为要从前往后放结果，所以需要做一个转换，再把多余的零弹出，再反向转换到字符串

从后往前遍历的index转换为从前往后的对应位置是size - index - 1
两个数组都是一样，所以

idx = num1.size() - i - 1 + num2.size() - j - 1 
    = num1.size() + num2.size() - i - i - 2

string multiply(string num1, string num2) {
    vector<int> mul(num1.size() + num2.size());
    for (int i = num1.size() - 1; i >= 0; i--) {
        for (int j = num2.size() - 1; j >= 0; j--) {
            int idx = num1.size() + num2.size() - i - j - 2;
            mul[idx] += (num1[i] - '0') * (num2[j] - '0');  // 要用+=
            if (mul[idx] > 9) {     // 需要进位
                mul[idx + 1] += mul[idx] / 10;  // 要用+=
                mul[idx] %= 10;
            }
        }
    }
    while (!mul.empty() && mul.back() == 0) {
        mul.pop_back();     // 除去多余的0
    }
    if (mul.empty()) return "0";
    
    string res;
    for (int i = mul.size() - 1; i >= 0; i--) {
        res.push_back(mul[i] + '0');    // 反转
    }
    return res;
}