力扣第43题“字符串相乘”

力扣第43题“字符串相乘”

题目要求

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

示例：

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

解题思路

1. 模拟手算乘法：我们将每一位相乘，然后把结果存入一个数组中，最后转换成字符串。
2. 进位处理：将数组中各个位置的数值按照进位规则进行调整。
3. 跳过前导零：结果中可能会出现前导零，需要跳过这些零并将剩下的部分转换成字符串。

代码实现

以下是详细的代码实现和逐行解释：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 字符串相乘函数
char* multiply(char* num1, char* num2) {
    int len1 = strlen(num1);
    int len2 = strlen(num2);
    int totalLen = len1 + len2;
    
    // 创建数组来存储乘积的各个位的数值
    int* result = (int*)calloc(totalLen, sizeof(int));
    
    // 从个位开始逐位相乘
    for (int i = len1 - 1; i >= 0; i--) {
        for (int j = len2 - 1; j >= 0; j--) {
            int mul = (num1[i] - '0') * (num2[j] - '0');
            int p1 = i + j;
            int p2 = i + j + 1;
            
            // 叠加到当前位置的值，并处理进位
            int sum = mul + result[p2];
            result[p2] = sum % 10;
            result[p1] += sum / 10;
        }
    }
    
    // 跳过前导零
    int start = 0;
    while (start < totalLen && result[start] == 0) {
        start++;
    }
    
    // 若结果为零，则直接返回 "0"
    if (start == totalLen) {
        free(result);
        return strdup("0");
    }
    
    // 转换结果为字符串
    char* product = (char*)malloc((totalLen - start + 1) * sizeof(char));
    for (int i = start; i < totalLen; i++) {
        product[i - start] = result[i] + '0';
    }
    product[totalLen - start] = '\0';
    
    free(result);
    return product;
}

// 测试代码
int main() {
    char num1[] = "123";
    char num2[] = "456";
    
    char* result = multiply(num1, num2);
    printf("结果: %s\n", result);
    
    free(result);
    return 0;
}

代码解析

1. 数组存储结果：

   int* result = (int*)calloc(totalLen, sizeof(int));
   

   创建一个大小为 len1 + len2 的数组 result，用于存储相乘结果的每个位的数值。

2. 逐位相乘并叠加：

   for (int i = len1 - 1; i >= 0; i--) {
       for (int j = len2 - 1; j >= 0; j--) {
           int mul = (num1[i] - '0') * (num2[j] - '0');
           int p1 = i + j;
           int p2 = i + j + 1;
           
           int sum = mul + result[p2];
           result[p2] = sum % 10;
           result[p1] += sum / 10;
       }
   }
   

   • 外层循环遍历 num1 的每一位，内层循环遍历 num2 的每一位。
   • 计算 num1[i] 和 num2[j] 的乘积，将结果添加到 result 数组的对应位置，处理进位。

3. 跳过前导零：

   int start = 0;
   while (start < totalLen && result[start] == 0) {
       start++;
   }
   

   计算后的 result 数组中可能包含前导零，找到第一个非零位置。

4. 转换结果为字符串：

   char* product = (char*)malloc((totalLen - start + 1) * sizeof(char));
   for (int i = start; i < totalLen; i++) {
       product[i - start] = result[i] + '0';
   }
   product[totalLen - start] = '\0';
   

   • 分配 product 字符串并将 result 数组中非零部分的每一位转为字符，最后在末尾加上字符串结束符 \0。

5. 特殊情况检查：
   如果结果中全为零，直接返回字符串 "0"。

复杂度分析

• 时间复杂度：O(n * m)，其中 n 和 m 分别为 num1 和 num2 的长度。
• 空间复杂度：O(n + m)，用于存储结果的数组 result 和最终的结果字符串。