算法的重要性，我就不多說了吧，想去大廠，就必須要經(jīng)過基礎(chǔ)知識和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個公眾號后續(xù)每天帶大家做一道算法題，題目就從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.
題意
給定兩個以字符串形式表示的非負(fù)整數(shù) num1 和 num2，返回 num1 和 num2 的乘積，它們的乘積也表示為字符串形式。樣例
示例 1:
輸入: num1 = "2", num2 = "3"
輸出: "6"
示例?2:
輸入: num1 = "123", num2 = "456"
輸出: "56088"
num1 和 num2 的長度小于110。
num1 和 num2 只包含數(shù)字 0-9。
num1 和 num2 均不以零開頭，除非是數(shù)字 0 本身。
不能使用任何標(biāo)準(zhǔn)庫的大數(shù)類型（比如 BigInteger）或直接將輸入轉(zhuǎn)換為整數(shù)來處理。
解題
https://www.cnblogs.com/techflow/p/12544184.html高精度與打豎式
這就需要我們的高精度算法出場了，其實嚴(yán)格說起來高精度并不是一種算法，而是一種思想。這個思想非常樸素，我敢保證我們每一個人都學(xué)過。還記得小學(xué)的時候，我們計算多位數(shù)的乘法是怎么算的嗎？大家應(yīng)該都不陌生才對，就是打豎式，like this：
我們?nèi)祟愐蜇Q式是因為我們只能計算一位數(shù)以內(nèi)的加減乘除，超過一位的人腦不能直接計算，我們就需要用紙筆記錄下來進行計算。紙筆計算的方法很簡單，就是一位一位地計算，用每一位數(shù)字依次去計算乘法，最后再移位相加起來就得到結(jié)果了。比如在上圖的第一個例子當(dāng)中，我們要計算15 * 16，我們先計算6 * 15的結(jié)果，再計算1 * 15，最后將兩個結(jié)果錯位相加，就得到了答案。我們要錯位的原因也很簡單，因為我們在計算15 * 1的時候，其實背后代表的是15 * 10。我們繼續(xù)拆分問題，當(dāng)我們計算6和15相乘的時候，又是怎么計算的呢？順著這個思路，整個過程可以進一步被劃分成先計算6和5相乘，再計算6和1相乘。最后，我們把兩個較大數(shù)字的相乘拆分成了在每一位上的數(shù)字相乘。到了這里，剩下的就簡單了，也就是說我們可以把這兩個很大的數(shù)字用兩個數(shù)組來存儲，數(shù)組當(dāng)中的每一位存儲數(shù)字上的一位。比如我們要計算123 * 224， 我們的第一個數(shù)組是[1, 2, 3]，我們的第二個數(shù)組是[2, 2, 4]。我們仿照乘法豎式中的方法計算這兩個數(shù)組當(dāng)中兩兩的乘積，并將它們拼裝成答案。123
* 224
____________
492
246
246
____________
27552
同樣我們用數(shù)組來存儲中間和最后的結(jié)果，最后的結(jié)果就是：[2, 7, 5, 5, 2]。由于題目需要我們要返回的是字符串，所以我們還需要將數(shù)組里的內(nèi)容再拼接成字符串。這種用數(shù)組來模擬數(shù)字進行加減乘除運算的方法就叫做高精度算法，相信大家也都看到了，嚴(yán)格說起來這并不是一個算法，而只是一種思想。今天的題目出的是乘法，我們利用同樣的方法也可以計算加減和除法。其中加減法非常簡單，而除法則要復(fù)雜得多，也是高精度當(dāng)中最難實現(xiàn)的部分。這里我們不做過多的拓展，計算的方法同樣是打豎式，感興趣的同學(xué)可以自行實現(xiàn)。進位和前導(dǎo)零
當(dāng)我們理清楚了打豎式的方法之后，我們還要面臨進位和前導(dǎo)零的問題。進位應(yīng)該很容易理解，我們需要在計算乘法的時候判斷當(dāng)前位置的元素是否大于等于10，如果超過10的話，我們則需要進行進位。我們只需要將它除以10，得到的結(jié)果就是我們需要進位的值。除此之外就是前導(dǎo)零的問題，我們都知道除了零以外的合法數(shù)字是不允許首位出現(xiàn)0的，但是由于我們計算的是乘法，所以當(dāng)其中某一個數(shù)為0會得到整體的結(jié)果為0，但是表示在數(shù)組當(dāng)中則是多個0.舉個簡單的例子，比如123 * 0，最后得到的應(yīng)該是0，但是由于我們用數(shù)組表示了乘法運算當(dāng)中的每一位，并且還進行了加法計算，所以會導(dǎo)致出現(xiàn)000的結(jié)果。這種情況我們要做特殊的處理，不過這也不復(fù)雜。最后我們把上面所有的思路都整理一下，就可以得到結(jié)果了。class Solution:
def multiply(self, num1: str, num2: str) -> str:
# 將字符串轉(zhuǎn)化成數(shù)組
# 翻轉(zhuǎn)數(shù)組，因為我們用第0位表示個位
arr1 = [ord(i) - ord('0') for i in num1][:: -1]
arr2 = [ord(i) - ord('0') for i in num2][:: -1]
# 創(chuàng)建結(jié)果數(shù)組，可以證明結(jié)果的長度最多是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
# 最后把數(shù)組再轉(zhuǎn)化成字符串返回
# 去除前導(dǎo)零
result = ''.join(map(str, ret))[::-1].lstrip('0')
return result if len(result) > 0else'0'
今天的題只是Medium難度，并不算困難，會選這題的原因主要是為了高精度算法。高精度算法本身并不難，也并不常用即使是在算法比賽當(dāng)中也不常見。但是它給了我們一個思路，當(dāng)我們要計算的數(shù)值超過計算機目前承載能力的時候，我們還有什么方法？當(dāng)然這題我們也可以取巧，因為Python當(dāng)中內(nèi)置了大整數(shù)，當(dāng)它檢測到我們的計算結(jié)果超過范圍的時候，會自動轉(zhuǎn)化成大整數(shù)來進行計算。所以這題如果我們使用Python，可以只用幾行代碼搞定：class Solution:
def multiply(self, num1: str, num2: str) -> str:
num1 = int(num1)
num2 = int(num2)
return str(num1 * num2)
好了，今天的文章就到這里，如果覺得有所收獲，請順手點個在看或者轉(zhuǎn)發(fā)吧，你們的支持是我最大的動力。
