算法的重要性，我就不多說了吧，想去大廠，就必須要經過基礎知識和業務邏輯面試+算法面試。所以，為了提高大家的算法能力，這個公眾號后續每天帶大家做一道算法題，題目就從LeetCode上面選 ！

今天和大家聊的問題叫做?字符串相乘，我們先來看題面：

https://leetcode-cn.com/problems/multiply-strings/

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

題意

給定兩個以字符串形式表示的非負整數 num1 和 num2，返回 num1 和 num2 的乘積，它們的乘積也表示為字符串形式。

樣例

示例 1:
輸入: num1 = "2", num2 = "3"
輸出: "6"
示例?2:
輸入: num1 = "123", num2 = "456"
輸出: "56088"

說明：

• num1 和 num2 的長度小于110。

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

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

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

解題

來源：https://www.cnblogs.com/techflow/p/12544184.html

高精度與打豎式

這就需要我們的高精度算法出場了，其實嚴格說起來高精度并不是一種算法，而是一種思想。這個思想非常樸素，我敢保證我們每一個人都學過。還記得小學的時候，我們計算多位數的乘法是怎么算的嗎？大家應該都不陌生才對，就是打豎式，like this：

我們人類要打豎式是因為我們只能計算一位數以內的加減乘除，超過一位的人腦不能直接計算，我們就需要用紙筆記錄下來進行計算。紙筆計算的方法很簡單，就是一位一位地計算，用每一位數字依次去計算乘法，最后再移位相加起來就得到結果了。比如在上圖的第一個例子當中，我們要計算15 * 16，我們先計算6 * 15的結果，再計算1 * 15，最后將兩個結果錯位相加，就得到了答案。我們要錯位的原因也很簡單，因為我們在計算15 * 1的時候，其實背后代表的是15 * 10。我們繼續拆分問題，當我們計算6和15相乘的時候，又是怎么計算的呢？順著這個思路，整個過程可以進一步被劃分成先計算6和5相乘，再計算6和1相乘。最后，我們把兩個較大數字的相乘拆分成了在每一位上的數字相乘。到了這里，剩下的就簡單了，也就是說我們可以把這兩個很大的數字用兩個數組來存儲，數組當中的每一位存儲數字上的一位。比如我們要計算123 * 224， 我們的第一個數組是[1, 2, 3]，我們的第二個數組是[2, 2, 4]。我們仿照乘法豎式中的方法計算這兩個數組當中兩兩的乘積，并將它們拼裝成答案。

123
   *  224
  ____________492246246
  ____________27552

同樣我們用數組來存儲中間和最后的結果，最后的結果就是：[2, 7, 5, 5, 2]。由于題目需要我們要返回的是字符串，所以我們還需要將數組里的內容再拼接成字符串。這種用數組來模擬數字進行加減乘除運算的方法就叫做高精度算法，相信大家也都看到了，嚴格說起來這并不是一個算法，而只是一種思想。今天的題目出的是乘法，我們利用同樣的方法也可以計算加減和除法。其中加減法非常簡單，而除法則要復雜得多，也是高精度當中最難實現的部分。這里我們不做過多的拓展，計算的方法同樣是打豎式，感興趣的同學可以自行實現。

進位和前導零

當我們理清楚了打豎式的方法之后，我們還要面臨進位和前導零的問題。進位應該很容易理解，我們需要在計算乘法的時候判斷當前位置的元素是否大于等于10，如果超過10的話，我們則需要進行進位。我們只需要將它除以10，得到的結果就是我們需要進位的值。除此之外就是前導零的問題，我們都知道除了零以外的合法數字是不允許首位出現0的，但是由于我們計算的是乘法，所以當其中某一個數為0會得到整體的結果為0，但是表示在數組當中則是多個0.舉個簡單的例子，比如123 * 0，最后得到的應該是0，但是由于我們用數組表示了乘法運算當中的每一位，并且還進行了加法計算，所以會導致出現000的結果。這種情況我們要做特殊的處理，不過這也不復雜。最后我們把上面所有的思路都整理一下，就可以得到結果了。我們來看下代碼：

class Solution:def multiply(self, num1: str, num2: str) -> str:# 將字符串轉化成數組# 翻轉數組，因為我們用第0位表示個位
        arr1 = [ord(i) - ord('0') for i in num1][:: -1]
        arr2 = [ord(i) - ord('0') for i in num2][:: -1]# 創建結果數組，可以證明結果的長度最多是n + m
        n, m = len(arr1), len(arr2)
        ret = [0for i in range(n + m + 1)]for i in range(n):for j in range(m):# 按位相乘，計算進位
                ret[i + j] += arr1[i] * arr2[j]if ret[i+j] >= 10:
                    ret[i+j+1] += ret[i+j] // 10
                    ret[i+j] %= 10# 最后把數組再轉化成字符串返回# 去除前導零
        result = ''.join(map(str, ret))[::-1].lstrip('0')return result if len(result) > 0else'0'

今天的題只是Medium難度，并不算困難，會選這題的原因主要是為了高精度算法。高精度算法本身并不難，也并不常用即使是在算法比賽當中也不常見。但是它給了我們一個思路，當我們要計算的數值超過計算機目前承載能力的時候，我們還有什么方法？當然這題我們也可以取巧，因為Python當中內置了大整數，當它檢測到我們的計算結果超過范圍的時候，會自動轉化成大整數來進行計算。所以這題如果我們使用Python，可以只用幾行代碼搞定：

class Solution:def multiply(self, num1: str, num2: str) -> str:
        num1 = int(num1)
        num2 = int(num2)return str(num1 * num2)

好了，今天的文章就到這里，如果覺得有所收獲，請順手點個在看或者轉發吧，你們的支持是我最大的動力。

上期推文：

LeetCode1-20題匯總，速度收藏！LeetCode21-40題匯總，速度收藏！LeetCode刷題實戰40：組合總和 IILeetCode刷題實戰41：缺失的第一個正數LeetCode刷題實戰42：接雨水