2024/4/5—力扣—字符串相乘

代码实现：

方法一：常规解法——超出整数表示范围

long long char_to_num(char *str) {
    long long num = 0;
    for (int i = 0; i < strlen(str); i++) {
        num = num * 10 + (str[i] - '0');
    }
    return num;
}

char* multiply(char *num1, char *num2) {
    long long a = char_to_num(num1), b = char_to_num(num2);
    long long c = a * b;
    if (c == 0) {
        return "0";
    }
    char *res = malloc(sizeof(char) * strlen(num1) + strlen(num2) + 3);
    int n = 0;
    while (c) {
        res[n++] = c % 10 + '0';
        c /= 10;
    }
    for (int i = 0; i < n / 2; i++) {
        int t = res[i];
        res[i] = res[n - 1 - i];
        res[n - 1 - i] = t;
    }
    res[n] = 0;
    return res;
}

方法二：(字符串模拟） O(n∗m)

1. 普通竖式

以num1 = 123 , num2 = 456为例：我们遍历 num2 每一位与 num1 进行相乘，将每一步的结果进行累加，在这个过程如果相乘或者相加的结果大于等于10 ，我们都要去满10进位

char *multiply(char *num1, char *num2) {
    int len1 = strlen(num1), len2 = strlen(num2);
    char *ans = (char*)malloc((len1 + len2 + 1) * sizeof(char));
    memset(ans, '0', sizeof(char) * (len1 + len2));
    ans[len1 + len2] = '\0';
    int c = 0;
    for (int i = len2 - 1; i >= 0; i--) {
        int b = num2[i] - '0';
        for (int j = len1 - 1; j >= 0; j--) {
            int a = num1[j] - '0';
            int d = ans[i + j + 1] - '0';
            int x = a * b + d + c;
            ans[i + j + 1] = x % 10 + '0';
            c = x / 10;
        }
        if (c) {
            ans[i] = c + '0';
            c = 0;
        }
    }
    // 去除前缀0
    int k = 0;
    while (ans[k] == '0' && k <= len1 + len2) {
        k++;
    }  
    if (k == len1 + len2) {
        return "0";
    } else {
        ans += k;
    }
    return ans;
}

2. 优化竖式

其实在相乘或者相加计算过程的每一位，可以考虑先不去满10进位，等到计算完所有的相乘结果以后，最终将其加到一块，再去满10进位 ，最后的结果和普通竖式 一样，但却可以大大简化我们的模拟过程

具体过程如下：

1. 长度是n和长度是m的数字相乘，最多只有n + m位，为了方便计算，将num1和num2反向存储到A[]和B[]中，即位数低的在数组前面，且开一个大小是n + m的C[]存储计算后的答案
2. 两个数相乘时，将A[i] * B[j]的结果累加到C[i + j]中，最后C[i + j]表示i + j这个位数的值是C[i + j](如上图所示)
3. 由于C[]数组中的某些位数字可能是大于等于10的，我们从0枚举到n + m - 1，进行满10进位， 将所有位的值全部变成个位数
4. 最后将C[]数组反转输出

细节：

最终得到的数组C[]的高位可能包含前导0，因此在反转之前要先去除高位前导0

时间复杂度分析： O(n∗m)，n和m分别是num1和num2的长度