字符串乘法

先看一道題

說明：

num1 和 num2 的長度小于110。

num1 和 num2 只包含數字 0-9。

num1 和 num2 均不以零開頭，除非是數字 0 本身。

不能使用任何標準庫的大數類型（比如 BigInteger）或直接將輸入轉換為整數來處理。

比如說我們手撕 123 × 45，應該會這樣計算：

你看這個簡單過程，其中涉及乘法進位，涉及錯位相加，還涉及加法進位；而且還有一些不易察覺的問題，比如說兩位數乘以兩位數，結果可能是四位數，也可能是三位數，你怎么想出一個標準化的處理方式？這就是算法的魅力，如果沒有計算機思維，簡單的問題可能都沒辦法自動化處理。

首先，我們這種手撕方式還是太「高級」了，我們要再「低級」一點，123 × 5 和 123 × 4 的過程還可以進一步分解，最后再相加：

現在 123 并不大，如果是個很大的數字的話，是無法直接計算乘積的。我們可以用一個數組在底下接收相加結果：

整個計算過程大概是這樣，有兩個指針 i，j 在 num1 和 num2 上游走，計算乘積，同時將乘積疊加到 res 的正確位置：

現在還有一個關鍵問題，如何將乘積疊加到 res 的正確位置，或者說，如何通過 i，j 計算 res 的對應索引呢？

其實，細心觀察之后就發現，num1[i] 和 num2[j] 的乘積對應的就是 res[i+j] 和 res[i+j+1] 這兩個位置。

就可以用代碼模仿出這個計算過程：

string multiply(string num1, string num2) {int m = num1.size(), n = num2.size();// 結果最多為 m + n 位數vector<int> res(m + n, 0);// 從個位數開始逐位相乘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;}// 結果前綴可能存的 0（未使用的位）int i = 0;while (i < res.size() && res[i] == 0)i++;// 將計算結果轉化成字符串string str;for (; i < res.size(); i++)str.push_back('0' + res[i]);return str.size() == 0 ? "0" : str; }

總結

以上是生活随笔為你收集整理的字符串乘法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。