讀完本文，你可以去力扣拿下如下題目：
-----------
對于比較小的數(shù)字，做運算可以直接使用編程語言提供的運算符，但是如果相乘的兩個因數(shù)非常大，語言提供的數(shù)據(jù)類型可能就會溢出。一種替代方案就是，運算數(shù)以字符串的形式輸入，然后模仿我們小學學習的乘法算術過程計算出結(jié)果，并且也用字符串表示。
需要注意的是，num1 和 num2 可以非常長，所以不可以把他們直接轉(zhuǎn)成整型然后運算，唯一的思路就是模仿我們手算乘法。
比如說我們手算 123 × 45，應該會這樣計算：
計算 123 × 5，再計算 123 × 4，最后錯一位相加。這個流程恐怕小學生都可以熟練完成，但是你是否能把這個運算過程進一步機械化，寫成一套算法指令讓沒有任何智商的計算機來執(zhí)行呢？
PS：我認真寫了 100 多篇原創(chuàng)，手把手刷 200 道力扣題目，全部發(fā)布在 labuladong的算法小抄，持續(xù)更新。建議收藏，按照我的文章順序刷題，掌握各種算法套路后投再入題海就如魚得水了。
你看這個簡單過程，其中涉及乘法進位，涉及錯位相加，還涉及加法進位；而且還有一些不易察覺的問題，比如說兩位數(shù)乘以兩位數(shù)，結(jié)果可能是四位數(shù)，也可能是三位數(shù)，你怎么想出一個標準化的處理方式？這就是算法的魅力，如果沒有計算機思維，簡單的問題可能都沒辦法自動化處理。
首先，我們這種手算方式還是太「高級」了，我們要再「低級」一點，123 × 5 和 123 × 4 的過程還可以進一步分解，最后再相加：
現(xiàn)在 123 并不大，如果是個很大的數(shù)字的話，是無法直接計算乘積的。我們可以用一個數(shù)組在底下接收相加結(jié)果：
整個計算過程大概是這樣，有兩個指針 i，j 在 num1 和 num2 上游走，計算乘積，同時將乘積疊加到 res 的正確位置：
現(xiàn)在還有一個關鍵問題，如何將乘積疊加到 res 的正確位置，或者說，如何通過 i，j 計算 res 的對應索引呢？
其實，細心觀察之后就發(fā)現(xiàn)，num1[i] 和 num2[j] 的乘積對應的就是 res[i+j] 和 res[i+j+1] 這兩個位置。
明白了這一點，就可以用代碼模仿出這個計算過程了：
string multiply(string num1, string num2) {
int m = num1.size(), n = num2.size();
// 結(jié)果最多為 m + n 位數(shù)
vector<int> res(m + n, 0);
// 從個位數(shù)開始逐位相乘
for (int i = m - 1; i >= 0; i--)
for (int j = n - 1; j >= 0; j--) {
int mul = (num1[i]-'0') * (num2[j]-'0');
// 乘積在 res 對應的索引位置
int p1 = i + j, p2 = i + j + 1;
// 疊加到 res 上
int sum = mul + res[p2];
res[p2] = sum % 10;
res[p1] += sum / 10;
}
// 結(jié)果前綴可能存的 0（未使用的位）
int i = 0;
while (i < res.size() && res[i] == 0)
i++;
// 將計算結(jié)果轉(zhuǎn)化成字符串
string str;
for (; i < res.size(); i++)
str.push_back('0' + res[i]);
return str.size() == 0 ? "0" : str;
}
至此，字符串乘法算法就完成了。
PS：我認真寫了 100 多篇原創(chuàng)，手把手刷 200 道力扣題目，全部發(fā)布在 labuladong的算法小抄，持續(xù)更新。建議收藏，按照我的文章順序刷題，掌握各種算法套路后投再入題海就如魚得水了。
總結(jié)一下，我們習以為常的一些思維方式，在計算機看來是非常難以做到的。比如說我們習慣的算術流程并不復雜，但是如果讓你再進一步，翻譯成代碼邏輯，并不簡單。算法需要將計算流程再簡化，通過邊算邊疊加的方式來得到結(jié)果。
俗話教育我們，不要陷入思維定式，不要程序化，要發(fā)散思維，要創(chuàng)新。但我覺得程序化并不是壞事，可以大幅提高效率，減小失誤率。算法不就是一套程序化的思維嗎，只有程序化才能讓計算機幫助我們解決復雜問題呀！
也許算法就是一種尋找思維定式的思維吧，希望本文對你有幫助。
＿＿＿＿＿＿＿＿＿＿＿＿＿
我的 在線電子書 有 100 篇原創(chuàng)文章，手把手帶刷 200 道力扣題目，建議收藏！對應的 GitHub 算法倉庫 已經(jīng)獲得了 70k star，歡迎標星！
