欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C++基于字符串實(shí)現(xiàn)大數(shù)相乘問題的代碼詳解

 更新時(shí)間:2025年03月31日 11:21:23   作者:倔強(qiáng)的石頭_  
在實(shí)際編程中,我們經(jīng)常會(huì)遇到需要處理大整數(shù)的情況,由于編程語言中內(nèi)置整數(shù)類型有其表示范圍的限制,當(dāng)需要處理的整數(shù)超出這些范圍時(shí),就不能直接使用內(nèi)置類型進(jìn)行計(jì)算,所以本文給大家介紹了相關(guān)的解決方法,需要的朋友可以參考下

一、問題描述

在實(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)文章!

相關(guān)文章

  • 解析C++類內(nèi)存分布

    解析C++類內(nèi)存分布

    本篇文章介紹了C++類內(nèi)存分布結(jié)構(gòu),我們來看看編譯器是怎么處理類成員內(nèi)存分布的,特別是在繼承、虛函數(shù)存在的情況下
    2021-06-06
  • C++ Boost Pool超詳細(xì)講解

    C++ Boost Pool超詳細(xì)講解

    Boost是為C++語言標(biāo)準(zhǔn)庫提供擴(kuò)展的一些C++程序庫的總稱。Boost庫是一個(gè)可移植、提供源代碼的C++庫,作為標(biāo)準(zhǔn)庫的后備,是C++標(biāo)準(zhǔn)化進(jìn)程的開發(fā)引擎之一,是為C++語言標(biāo)準(zhǔn)庫提供擴(kuò)展的一些C++程序庫的總稱
    2022-11-11
  • C語言實(shí)現(xiàn)學(xué)生信息管理系統(tǒng)(單鏈表)

    C語言實(shí)現(xiàn)學(xué)生信息管理系統(tǒng)(單鏈表)

    這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)學(xué)生信息管理系統(tǒng),文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2018-01-01
  • C++使用HTTP庫和框架輕松發(fā)送HTTP請(qǐng)求

    C++使用HTTP庫和框架輕松發(fā)送HTTP請(qǐng)求

    使用C++編程發(fā)送HTTP請(qǐng)求通常需要使用第三方的HTTP庫或框架,本文主要介紹了C++使用HTTP庫和框架輕松發(fā)送HTTP請(qǐng)求,感興趣的可以了解一下
    2023-12-12
  • 詳解C++標(biāo)準(zhǔn)庫中處理正則表達(dá)式的類std::regex

    詳解C++標(biāo)準(zhǔn)庫中處理正則表達(dá)式的類std::regex

    std?是?C++?標(biāo)準(zhǔn)庫的命名空間,包含了大量標(biāo)準(zhǔn)的?C++?類、函數(shù)和對(duì)象,這些類和函數(shù)提供了廣泛的功能,包括輸入輸出、容器、算法、字符串處理等,這篇文章主要介紹了C++標(biāo)準(zhǔn)庫中提供的用于處理正則表達(dá)式的類std::regex,需要的朋友可以參考下
    2024-03-03
  • C++實(shí)現(xiàn)插入排序?qū)φ麛?shù)數(shù)組排序

    C++實(shí)現(xiàn)插入排序?qū)φ麛?shù)數(shù)組排序

    這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)插入排序?qū)φ麛?shù)數(shù)組排序,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2020-05-05
  • C語言實(shí)現(xiàn)個(gè)人通訊錄管理系統(tǒng)

    C語言實(shí)現(xiàn)個(gè)人通訊錄管理系統(tǒng)

    這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)個(gè)人通訊錄管理系統(tǒng),文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2019-12-12
  • QT .pro文件的實(shí)現(xiàn)

    QT .pro文件的實(shí)現(xiàn)

    本文主要介紹了QT .pro文件的實(shí)現(xiàn),文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2023-01-01
  • C++中的std::initializer_list使用解讀

    C++中的std::initializer_list使用解讀

    這篇文章主要介紹了C++中的std::initializer_list使用,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
    2023-07-07
  • 在C語言中對(duì)utmp文件進(jìn)行查找和寫入操作的函數(shù)小結(jié)

    在C語言中對(duì)utmp文件進(jìn)行查找和寫入操作的函數(shù)小結(jié)

    這篇文章主要介紹了在C語言中對(duì)utmp文件進(jìn)行查找和寫入操作的函數(shù)小結(jié),包括pututline()函數(shù)和getutline()函數(shù)以及getutid()函數(shù),需要的朋友可以參考下
    2015-08-08

最新評(píng)論