經典問題大數(shù)乘法

給兩個字符串格式的十進制數(shù)字，求這兩個數(shù)的乘積，以字符串格式返回。
leetcode問題鏈接
本篇教你看一遍永遠忘不了的大數(shù)乘法解法，以及如何將運行時間優(yōu)化到0ms。

思路

既然是大數(shù)，無法放到整數(shù)類型的變量中，這時我們的小學知識終于派上了用場！還記得怎么筆算乘法嗎？如果不記得，好好回憶一下整個步驟。

乘法筆算

我們要做的，就是把這種筆算方法轉成代碼，就可以解決這個問題了，聽上去一點也不難吧？

為什么面試做不出來

然而在面試過程中，很多人都做不出來這道題，這是為什么？
其實思路大家都想得到，只是這看似簡單的筆算，其實包含了很多步驟。如果沒有把他們理清楚，一步一步地去實現(xiàn)，就很容易把自己繞暈。

步驟拆解

第一步：格式轉換

算法的核心是把多位數(shù)的乘法轉化成很多一位數(shù)的乘法，然后加起來。于是我們需要先吧字符串的每一位轉成數(shù)字，方便計算乘法。
例如：字符串 "123456789" 要轉成整數(shù)列表 [1,2,3,4,5,6,7,8,9]

第二步：計算大數(shù)與一位數(shù)的乘積

對應上圖筆算乘法，就是要計算 145 * 2 = 290，還有145 * 1 = 145 這兩個步驟。
只要按照從低位到高位的順序去乘就好了，注意處理進位。

第三步：計算大數(shù)加法

對應上圖筆算中把290與145相加的步驟。
沒錯，要做大數(shù)乘法，首先得會做大數(shù)加法。其實很簡單，只要從低位到高位一位一位地相加，注意進位就可以了。

第四步：格式轉換

前面計算過程中全部用的是整數(shù)列表的格式，計算完成后再把格式轉成字符串就可以了。

開始擼代碼吧，記得按步驟來

下面代碼使用go語言

1. 格式轉換

這一步沒什么好說的

func convertStringToIntDigitList(stringNum string) []int64 {
    digitList := make([]int64, 0)
    for i:=0; i<len(stringNum); i++ {
        digitList = append(digitList, int64(stringNum[i]-'0'))
    }
    return digitList
}

2. 計算大數(shù)與一位數(shù)的乘積

這一步要注意的是：以及處理好進位，包括最高位的進位。

const base=10
func multiplyDigitListByDigit(digitList []int64, digit int64) []int64 {
    if digit == 0 { // 處理邊界情況
        return make([]int64, 0)
    }
    var c int64
    product := make([]int64, len(digitList))
    for i := len(digitList) - 1; i>=0; i-- {
        p := digitList[i] * digit + c // 加上低位的進位
        c = p / base // 進位
        product[i] = p % base
    }
    if c > 0 {
        // 如果還有進位，在最高位加一位
        product = append([]int64{c}, product...)
    }
    return product
}

3. 計算大數(shù)加法

const base=10
func addTwoDigitLists(digitList1, digitList2 []int64) []int64 {
    sum := make([]int64, 0)
    var c int64
    for i := 0; i<len(digitList1) || i < len(digitList2); i++ {
        var d1, d2 int64
        if i < len(digitList1) {
            d1 = digitList1[len(digitList1)-i-1]
        }
        if i < len(digitList2) {
            d2 = digitList2[len(digitList2)-i-1]
        }
        s := d1+d2+c
        sum = append([]int64{s%base}, sum...)
        c = s / base
    }
    if c > 0 {
        sum = append([]int64{c}, sum...)
    }
    return sum
}

4. 格式轉換回字符串

func convertDigitListToString(digitList []int64) string {
    numStr := ""
    for i:=0; i<len(digitList); i++ {
        numStr += string(byte(digitList[i] + '0'))
    }
    // 注意處理前導0和結果為0的情況
    numStr = strings.TrimLeft(numStr, "0")
    if numStr == "" {
        return "0"
    }
    return numStr
}

5. 最后，將這些步驟整合

func multiply(numStr1, numStr2 string) string {
    num1 := convertStringToIntDigitList(numStr1)
    num2 := convertStringToIntDigitList(numStr2)
    products := make([][]int64, 0)
    for i:=0; i<len(digitList2); i++ {
        prod := multiplyDigitListByDigit(digitList1, digitList2[len(digitList2)-1-i])
        product := append(prod, make([]int64, i)...) // 末尾補0
        products = append(products, product)
    }
    result := make([]int64, 0)
    for _, product := range products {
        result = addTwoDigitLists(product, result)
    }
    return convertDigitListToString(result)
}

總結

雖然代碼行數(shù)看起來也不少，但步驟清晰，其中每一步都很簡單，看過一遍之后，你還會忘記嗎？這就是問題分解的魅力，大題化小，小題化了，一個問題分解成多個很簡單的小問題。
當然，我們也可以將這些函數(shù)全部合并到同一個函數(shù)里面，如果這樣做，不僅代碼行數(shù)減少了，而且代碼中會少很多內存分配的步驟，導致內存占用和運行時間都會減少，但代價是更不容易記憶，這當然算追求極致，但對于以面試為目的同學，記得牢才更重要。

進階，如何優(yōu)化運行時間？

上面介紹的算法，便于記憶且寫法相對簡單，但性能還有很大的提升空間。我們代碼中用int64來存儲數(shù)字，但只用來進行一位數(shù)的計算。如果能一次計算多位，就能減少計算次數(shù)。
可能有人已經注意到，我在代碼中定義了一個base的常量為10，代表每個int64只存儲一位數(shù)。如果將base改成10000，每個int64就可以存儲四位數(shù)。但同時，兩個convert函數(shù)也需要修改，四位四位地轉換。

優(yōu)化后的格式轉化函數(shù)

func convertStringToIntDigitList(stringNum string) []int64 {
    digitList := make([]int64, 0)
    for i:=len(stringNum)-1; i>=0; i-=4 {
        a := 0
        if i >= 4 {
            a = i-4+1
        }
        s := stringNum[a:i+1]
        d, _ := strconv.ParseInt(s, 10, 64)
        digitList = append([]int64u0z1t8os, digitList...)
    }
    return digitList
}

func convertDigitListToString(digitList []int64) string {
    numStr := ""
    for i:=0; i<len(digitList); i++ {
        numStr += fmt.Sprintf("%04d", digitList[i]) // 如果不夠4位，需要在前面補0
    }
    strings.TrimLeft(numStr, "0")
    if numStr == "" {
        return "0"
    }
    return numStr
}

到底能減少多少時間？

這樣依賴，我們可以減少多少次計算呢？
假設兩個大數(shù)分別有m位和n位，按照原來的算法需要計算m * n 次乘法，以及n次加法，而新的算法只需要(m/4) * (n/4)次乘法和(n/4)次加法，如果只看乘法，計算次數(shù)只有原來的1/16！
同時，存儲所需的空間也會減少。原來的算法需要為大數(shù)分配(m+n)個int64空間，新的算法只需要四分之一。

優(yōu)化的極限

按照這種思路，最多一組幾位數(shù)呢？那就要看int64能裝下多少了。眾所周知，int64能表示的最大整數(shù)是2^63-1也就是9223372036854775807，十進制是19位數(shù)。但需要注意的是，在我們的算法中會出現(xiàn)兩個int64相乘的計算，也就是我們最多只能存9位數(shù)，這樣兩個9位數(shù)相乘最多得到18位數(shù)，不會超出int64的范圍。
于是我們把base改成1e9(10的9次方)，兩個convert函數(shù)也做相應的修改，就可以得到打敗100%網友的代碼了。