当前位置：首页 > article >正文

【OJ题解】C++实现字符串大数相乘：无BigInteger库的字符串乘积解决方案

article 2024/12/26 0:53:34

🦄个人主页: 起名字真南
🦄个人专栏:【数据结构初阶】【C语言】【C++】【OJ题解】

请添加图片描述

1. 引言

在开发中，有时我们需要处理超出标准整数范围的大数运算。例如，两个200位的数字相乘，结果可能多达400位，而这远超出int或long的存储能力。本教程将深入讲解如何使用C++实现字符串形式的数字相乘，完全不依赖BigInteger或类似大数库的支持。

2. 题目分析

题目要求我们给定两个非负整数字符串num1和num2，返回它们的乘积结果字符串。考虑到每个字符串长度可能达200位，所以乘积结果最多有400位，我们不能简单地将字符串转成整数相乘。相反，我们可以通过模拟手动乘法的方式来解决这个问题。

C++实现字符串大数相乘题目链接

示例：

示例 1：
- 输入：num1 = "2"，num2 = "3"
- 输出："6"
示例 2：
- 输入：num1 = "123"，num2 = "456"
- 输出："56088"

3. 解题思路

该题目可以用模拟手动乘法来实现。我们可以把计算步骤划分如下：

逐位相乘：倒序遍历两个字符串，将每一位相乘，计算出相应的部分积。
累加进位：在累加结果时，处理进位并确保每个位的值不超过9。
去除前导零：最终结果可能有前导零，将其去除。

4. C++代码实现

以下为详细的C++代码实现：

class Solution {
public:
    string multiply(string num1, string num2) {
        // 特殊情况：如果任意一个数字为 "0"，返回 "0"
        if (num1 == "0" || num2 == "0") {
            return "0";
        }
        
        // 初始化结果字符串，长度为 num1.size() + num2.size()
        size_t n1 = num1.size();
        size_t n2 = num2.size();
        string result(n1 + n2, '0');
        
        // 倒序遍历 num1 和 num2
        for (int i = n1 - 1; i >= 0; i--) {
            for (int j = n2 - 1; j >= 0; j--) {
                // 将字符转换为整数
                int x = num1[i] - '0';
                int y = num2[j] - '0';
                int mul = x * y; // 单个位的乘积
                
                // 确定结果中的位置
                int p1 = i + j;       // 进位位置
                int p2 = i + j + 1;   // 当前位位置
                
                // 叠加当前的乘积到结果
                int sum = mul + (result[p2] - '0');
                result[p2] = (sum % 10) + '0';    // 当前位
                result[p1] += sum / 10;           // 进位
            }
        }
        
        // 去除前导零
        size_t startpos = result.find_first_not_of('0');
        if (startpos != string::npos) {
            return result.substr(startpos);
        }
        
        return "0";
    }
};

5. 代码详解

特殊情况处理：首先检查num1或num2是否为"0"，若是则直接返回"0"。
结果初始化：使用string result(n1 + n2, '0')初始化结果字符串，长度为n1 + n2，确保足够容纳乘积结果。初始值为’0’，便于后续累加操作。
倒序遍历相乘：
- 字符转数字：num1[i] - '0' 和 num2[j] - '0'用于将字符转为整数。
- 单个位乘积：计算单个位乘积 mul = x * y。
- 位置确定：p1和p2分别表示当前乘积的进位位置和当前位位置。
- 累加到结果：通过sum = mul + (result[p2] - '0')将当前乘积叠加到结果字符串中，并更新result[p2]为当前位，同时将进位累加到result[p1]。
去除前导零：result.find_first_not_of('0')找到第一个非零位的索引，如果找到则返回从该位置截取的子字符串，否则返回"0"。