43.字符串相乘

题目要求

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

注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。

样例 #1

输入 #1

num1 = "2", num2 = "3"

输出 #1

"6"

样例 #2

输入 #2

num1 = "123", num2 = "456"

输出 #2

"56088"

提示

1 <= num1.length, num2.length <= 200
num1 和 num2 只能由数字组成。
num1 和 num2 都不包含任何前导零，除了数字0本身。

解法1

解题思路

将字符型数组变成整型直接相乘，在变为字符型数组，但是本题数据太大，无法用int存储

代码实现

char * multiply(char * num1, char * num2)
{
    int len1 = strlen (num1);
    int len2 = strlen (num2);
    int i, n1 = 0, n2 = 0, n, len = 0;
    char* num;
    for (i = 0; i < len1; i++){
        n1 = n1 * 10 + num1[i] - 48;
    }
    for (i = 0; i < len2; i++){
        n2 = n2 * 10 + num2[i] - 48;
    }
    n = n1 * n2;
    if (n == 0){
        len = 1;
    }else{
        while (n != 0 || n % 10 != 0){
            n = n / 10;
            len++;
        }
    }
    n = n1 * n2;
    num = malloc(sizeof(char) * (len + 1));
    for (i = len - 1; i >= 0; i--){
        num[i] = n % 10 + 48;
        n = n / 10;
    }
    num[len]='\0';
    return num;
}

解法2

解题思路

利用高精度乘法进行计算，注意数组的溢出以及字符型数组以\0结尾

代码实现

char * multiply(char * num1, char * num2){
    int len1 = strlen( num1 );
    int len2 = strlen( num2 );
    int len = len1 + len2;
    int i, j, k, x = 0;
    int *num;
    char *n;
    num = calloc( len, sizeof( int ) );
    for( i = len1 -1; i >= 0; i-- ){
        for( j = len2 - 1,k = x; j >= 0; j--, k++ ){
            num[k] = (num1[i] - 48) * (num2[j] - 48) + num[k];//逆序相乘正序储存
            if( num[k] > 9 && k +1 < len ){
                num[k+1] = num[k] / 10 + num[k+1];
                num[k] = num[k] % 10;
            }
        }
        x++;
    }
    if( num[len - 1] != 0 ){
        len++;
    }
    if( num[len - 2] == 0 ){
        n = malloc( sizeof( char ) * 2 );
        n[0]='0';
        n[1]='\0';//避免00000的出现
    }else{
        n = malloc( sizeof( char ) * len );
        for( i = 0; i < len -1; i++ ){
            n[i] = num[len - i - 2] + 48;//整型数组位数少
        }
        n[i] = '\0';
    }
    return n;
}