一、問題描述

在實(shí)際編程中，我們經(jīng)常會(huì)遇到需要處理大整數(shù)的情況。由于編程語言中內(nèi)置整數(shù)類型（如 int、long 等）有其表示范圍的限制，當(dāng)需要處理的整數(shù)超出這些范圍時(shí)，就不能直接使用內(nèi)置類型進(jìn)行計(jì)算。
一般的解決方式是以兩個(gè)以字符串形式表示的非負(fù)整數(shù) num1 和 num2 的乘法，并將結(jié)果也以字符串形式返回。

輸入限制

• 1 <= num1.length, num2.length <= 200
• num1 和 num2 只能由數(shù)字組成。
• num1 和 num2 都不包含任何前導(dǎo)零，除了數(shù)字 0 本身。

二、解題思路

要解決這個(gè)問題，我們可以模擬手工乘法的過程。在手工乘法中，我們將一個(gè)數(shù)的每一位與另一個(gè)數(shù)的每一位相乘，然后將結(jié)果相加，并處理進(jìn)位。具體步驟如下：

1. 特殊情況處理：如果 num1 或 num2 為 "0"，則直接返回 "0"。
2. 反轉(zhuǎn)字符串：為了方便從低位到高位進(jìn)行計(jì)算，我們將 num1 和 num2 反轉(zhuǎn)。
3. 初始化結(jié)果數(shù)組：創(chuàng)建一個(gè)長(zhǎng)度為 num1.size() + num2.size() 的數(shù)組 ret，用于存儲(chǔ)中間結(jié)果。因?yàn)閮蓚€(gè)數(shù)相乘的結(jié)果位數(shù)不會(huì)超過這兩個(gè)數(shù)的位數(shù)之和。
4. 逐位相乘：使用兩層循環(huán)，將 num1 的每一位與 num2 的每一位相乘，并將結(jié)果累加到 ret 數(shù)組的相應(yīng)位置。
5. 處理進(jìn)位：遍歷 ret 數(shù)組，將每一位的進(jìn)位加到下一位。
6. 去除前導(dǎo)零：由于結(jié)果數(shù)組可能存在前導(dǎo)零，我們需要將其去除。
7. 轉(zhuǎn)換為字符串：將處理好的結(jié)果數(shù)組轉(zhuǎn)換為字符串。

三、代碼實(shí)現(xiàn)

#include <string>
#include <algorithm>

class Solution {
public:
    string multiply(string num1, string num2) 
    {
        // 先判斷是否有一個(gè)為0
        if(num1 == "0" || num2 == "0")
            return "0";

        // 反轉(zhuǎn)兩個(gè)字符串方便操作
        reverse(num1.begin(), num1.end());
        reverse(num2.begin(), num2.end());

        // 結(jié)果位數(shù)不超過兩個(gè)字符串之和
        int size = num1.size() + num2.size();

        // 創(chuàng)建存儲(chǔ)結(jié)果的數(shù)組并初始化為0
        int* ret = new int[size]();
        
        // 字符串相乘，不考慮進(jìn)位
        for(int i = 0; i < num1.size(); ++i)
        {
            for(int j = 0; j < num2.size(); ++j)
            {
                ret[i + j] += (num1[i] - '0') * (num2[j] - '0');
            }
        }

        // 處理進(jìn)位
        for(int i = 0; i < size - 1; ++i)
        {
            ret[i + 1] += ret[i] / 10;
            ret[i] = ret[i] % 10;
        }
        
        // 去除前導(dǎo)零
        int i = size - 1;
        while( (ret[i] == 0) && (size > 1) )
        {
            --size;
            --i;
        }

        // 轉(zhuǎn)字符串
        string s = "";
        s.reserve(size);
        for(int i = size - 1; i >= 0; --i)
        {
            s += ('0' + ret[i]);
        }

        // 釋放動(dòng)態(tài)分配的內(nèi)存
        delete[] ret;
        return s;
    }
};

四、代碼詳細(xì)分析

1. 特殊情況處理

if(num1 == "0" || num2 == "0")
    return "0";

如果 num1 或 num2 為 "0"，則它們的乘積一定為 "0"，直接返回即可。

2. 反轉(zhuǎn)字符串

reverse(num1.begin(), num1.end());
reverse(num2.begin(), num2.end());

使用 std::reverse 函數(shù)將 num1 和 num2 反轉(zhuǎn)，這樣在后續(xù)計(jì)算中可以從低位（字符串的起始位置）開始處理。

3. 初始化結(jié)果數(shù)組

int size = num1.size() + num2.size();
int* ret = new int[size]();

建一個(gè)長(zhǎng)度為 num1.size() + num2.size() 的整數(shù)數(shù)組 ret，并使用 () 進(jìn)行值初始化，將數(shù)組元素都初始化為 0。

4. 逐位相乘

for(int i = 0; i < num1.size(); ++i)
{
    for(int j = 0; j < num2.size(); ++j)
    {
        ret[i + j] += (num1[i] - '0') * (num2[j] - '0');
    }
}

使用兩層嵌套循環(huán)，將 num1 的每一位與 num2 的每一位相乘，并將結(jié)果累加到 ret 數(shù)組的相應(yīng)位置。(num1[i] - '0') 和 (num2[j] - '0') 是將字符轉(zhuǎn)換為對(duì)應(yīng)的數(shù)字。

5. 處理進(jìn)位

for(int i = 0; i < size - 1; ++i)
{
    ret[i + 1] += ret[i] / 10;
    ret[i] = ret[i] % 10;
}

遍歷 ret 數(shù)組，將每一位的進(jìn)位（ret[i] / 10）加到下一位，同時(shí)將當(dāng)前位取模 10 得到該位的最終結(jié)果。

6. 去除前導(dǎo)零

int i = size - 1;
while( (ret[i] == 0) && (size > 1) )
{
    --size;
    --i;
}

從結(jié)果數(shù)組的最高位開始檢查，如果該位為 0 且結(jié)果長(zhǎng)度大于 1，則將長(zhǎng)度減 1，繼續(xù)檢查前一位。

7. 轉(zhuǎn)換為字符串

string s = "";
s.reserve(size);
for(int i = size - 1; i >= 0; --i)
{
    s += ('0' + ret[i]);
}

創(chuàng)建一個(gè)空字符串 s，并使用 reserve 方法預(yù)先分配足夠的空間。然后從結(jié)果數(shù)組的最高位開始，將每一位轉(zhuǎn)換為字符并添加到字符串 s 中。

8. 釋放內(nèi)存

delete[] ret;

由于 ret 是動(dòng)態(tài)分配的數(shù)組，使用完后需要使用 delete[] 釋放內(nèi)存，避免內(nèi)存泄漏。

五、復(fù)雜度分析

• 時(shí)間復(fù)雜度：O ( m ∗ n )，其中 m mm 和 n nn 分別是 num1 和 num2 的長(zhǎng)度。主要時(shí)間開銷在于兩層嵌套的循環(huán)進(jìn)行逐位相乘。
• 空間復(fù)雜度：O ( m + n )，主要空間開銷在于存儲(chǔ)中間結(jié)果的數(shù)組 ret。

通過以上步驟，我們就可以實(shí)現(xiàn)兩個(gè)大整數(shù)的乘法，并將結(jié)果以字符串形式返回。這種方法模擬了手工乘法的過程，避免了使用內(nèi)置的大整數(shù)庫和直接將輸入轉(zhuǎn)換為整數(shù)，適用于處理超出內(nèi)置整數(shù)類型表示范圍的大整數(shù)乘法問題。

以上就是C++基于字符串實(shí)現(xiàn)大數(shù)相乘問題的代碼詳解的詳細(xì)內(nèi)容，更多關(guān)于C++字符串實(shí)現(xiàn)大數(shù)相乘的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論