C++基于字符串實(shí)現(xiàn)大數(shù)相乘問題的代碼詳解
一、問題描述
在實(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)位。具體步驟如下:
- 特殊情況處理:如果
num1
或num2
為"0"
,則直接返回"0"
。 - 反轉(zhuǎn)字符串:為了方便從低位到高位進(jìn)行計(jì)算,我們將
num1
和num2
反轉(zhuǎn)。 - 初始化結(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ù)之和。 - 逐位相乘:使用兩層循環(huán),將
num1
的每一位與num2
的每一位相乘,并將結(jié)果累加到ret
數(shù)組的相應(yīng)位置。 - 處理進(jìn)位:遍歷
ret
數(shù)組,將每一位的進(jìn)位加到下一位。 - 去除前導(dǎo)零:由于結(jié)果數(shù)組可能存在前導(dǎo)零,我們需要將其去除。
- 轉(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語言實(shí)現(xiàn)學(xué)生信息管理系統(tǒng)(單鏈表)
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)學(xué)生信息管理系統(tǒng),文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2018-01-01C++使用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
std?是?C++?標(biāo)準(zhǔn)庫的命名空間,包含了大量標(biāo)準(zhǔn)的?C++?類、函數(shù)和對(duì)象,這些類和函數(shù)提供了廣泛的功能,包括輸入輸出、容器、算法、字符串處理等,這篇文章主要介紹了C++標(biāo)準(zhǔn)庫中提供的用于處理正則表達(dá)式的類std::regex,需要的朋友可以參考下2024-03-03C++實(shí)現(xiàn)插入排序?qū)φ麛?shù)數(shù)組排序
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)插入排序?qū)φ麛?shù)數(shù)組排序,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2020-05-05C語言實(shí)現(xiàn)個(gè)人通訊錄管理系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)個(gè)人通訊錄管理系統(tǒng),文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2019-12-12C++中的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é),包括pututline()函數(shù)和getutline()函數(shù)以及getutid()函數(shù),需要的朋友可以參考下2015-08-08