今天是LeetCode系列第22篇文章，今天講的內容是高精度算法。
今天和大家討論的算法是高精度，對應的LeetCode是第43題。題面其實沒什麼好說的，以字符串的形式給定兩個數字，要求返回這兩個數字的乘積。之所以是以字符串的形式給數字是因為這個數字可能會非常大，題目當中給定的範圍是110位的數字。對於Python來說這不是問題，但是對於C++和Java等語言來說這麼大的數字是無法以int類型存儲的，所以必須要使用字符串來接收。
如果你使用Python，你可以不用任何算法就AC這題，但是這沒有任何意義。那麼正確的方法應該怎麼做呢？
高精度與打豎式
這就需要我們的高精度算法出場了，其實嚴格說起來高精度並不是一種算法，而是一種思想。這個思想非常樸素，我敢保證我們每一個人都學過。還記得小學的時候，我們計算多位數的乘法是怎麼算的嗎？大家應該都不陌生才對，就是
打豎式，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]。我們仿照乘法豎式中的方法計算這兩個數組當中兩兩的乘積，並將它們拼裝成答案。
<code> 1 2 3
* 2 2 4
____________
4 9 2
2 4 6
2 4 6
____________
2 7 5 5 2/<code>
同樣我們用數組來存儲中間和最後的結果，最後的結果就是：[2, 7, 5, 5, 2]。由於題目需要我們要返回的是字符串，所以我們還需要將數組裡的內容再拼接成字符串。
這種用數組來模擬數字進行加減乘除運算的方法就叫做高精度算法，相信大家也都看到了，嚴格說起來這並不是一個算法，而只是一種思想。今天的題目出的是乘法，我們利用同樣的方法也可以計算加減和除法。其中加減法非常簡單，而除法則要複雜得多，也是高精度當中最難實現的部分。這裡我們不做過多的拓展，計算的方法同樣是打豎式，感興趣的同學可以自行實現。
進位和前導零
當我們理清楚了打豎式的方法之後，我們還要面臨進位和前導零的問題。
進位應該很容易理解，我們需要在計算乘法的時候判斷當前位置的元素是否大於等於10，如果超過10的話，我們則需要進行進位。我們只需要將它除以10，得到的結果就是我們需要進位的值。除此之外就是前導零的問題，我們都知道除了零以外的合法數字是不允許首位出現0的，但是由於我們計算的是乘法，所以當其中某一個數為0會得到整體的結果為0，但是表示在數組當中則是多個0.
舉個簡單的例子，比如123 * 0，最後得到的應該是0，但是由於我們用數組表示了乘法運算當中的每一位，並且還進行了加法計算，所以會導致出現000的結果。這種情況我們要做特殊的處理，不過這也不復雜。最後我們把上面所有的思路都整理一下，就可以得到結果了。
我們來看下代碼：
今天的題只是Medium難度，並不算困難，會選這題的原因主要是為了高精度算法。高精度算法本身並不難，也並不常用即使是在算法比賽當中也不常見。但是它給了我們一個思路，當我們要計算的數值超過計算機目前承載能力的時候，我們還有什麼方法？
當然這題我們也可以取巧，因為Python當中內置了大整數，當它檢測到我們的計算結果超過範圍的時候，會自動轉化成大整數來進行計算。所以這題如果我們使用Python，可以只用幾行代碼搞定：
今天關於高精度算法的內容就到這裡，如果覺得有所收穫，請順手點個關注或者轉發吧，你們的舉手之勞對我來說很重要。
閱讀更多 承志的算法課堂 的文章
