43. 字符串相乘

难度：中等

题目

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

示例 1:

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

示例 2:

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

说明：

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

Reference

题解

计算方法与列竖式相同，注意对特殊输入0的处理。结果的长度不会超过输入字符串长度之和。

char * multiply(char * num1, char * num2){
    if (*num1 == '0' || *num2 == '0')
        return *num1 == '0' ? num1 : num2;
    int len1 = strlen(num1), len2 = strlen(num2), retLen = len1 + len2, i = 0, j = 0, incre, curDigit, pos;
    char *ret = (char *)memset(malloc(sizeof(char) * (retLen + 1)), '0', sizeof(char) * (retLen + 1)),
         *cur = ret;
    ret[retLen] = 0;
    for (i = len1 - 1; i >= 0; i--)
    {
        for (j = len2 - 1; j >= 0; j--)
        {
            incre = (num1[i] - '0') * (num2[j] - '0');
            curDigit = incre % 10;
            incre /= 10;
            pos = retLen - ((len1 - i - 1) + (len2 - j - 1)) - 1;
            while (incre != 0 || curDigit != 0)
            {
                ret[pos] += curDigit;
                incre += ret[pos] > '9';
                ret[pos] -= ret[pos] > '9' ? 10 : 0;
                curDigit = incre >= 10 ? incre - 10 : incre;
                incre = incre >= 10;
                pos--;
            }
        }
    }
    while (*cur == '0')
        cur++;
    return cur;
}

评论