经典问题大数乘法
给两个字符串格式的十进制数字，求这两个数的乘积，以字符串格式返回。
leetcode问题链接
本篇教你看一遍永远忘不了的大数乘法解法，以及如何将运行时间优化到0ms。
思路
既然是大数，无法放到整数类型的变量中，这时我们的小学知识终于派上了用场！还记得怎么笔算乘法吗？如果不记得，好好回忆一下整个步骤。
乘法笔算
我们要做的，就是把这种笔算方法转成代码，就可以解决这个问题了，听上去一点也不难吧？
为什么面试做不出来
然而在面试过程中，很多人都做不出来这道题，这是为什么？
其实思路大家都想得到，只是这看似简单的笔算，其实包含了很多步骤。如果没有把他们理清楚，一步一步地去实现，就很容易把自己绕晕。
步骤拆解
第一步：格式转换
算法的核心是把多位数的乘法转化成很多一位数的乘法，然后加起来。于是我们需要先吧字符串的每一位转成数字，方便计算乘法。
例如：字符串 "123456789" 要转成整数列表 [1,2,3,4,5,6,7,8,9]
第二步：计算大数与一位数的乘积
对应上图笔算乘法，就是要计算 145 * 2 = 290，还有145 * 1 = 145 这两个步骤。
只要按照从低位到高位的顺序去乘就好了，注意处理进位。
第三步：计算大数加法
对应上图笔算中把290与145相加的步骤。
没错，要做大数乘法，首先得会做大数加法。其实很简单，只要从低位到高位一位一位地相加，注意进位就可以了。
第四步：格式转换
前面计算过程中全部用的是整数列表的格式，计算完成后再把格式转成字符串就可以了。
开始撸代码吧，记得按步骤来
下面代码使用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. 计算大数与一位数的乘积
这一步要注意的是：以及处理好进位，包括最高位的进位。
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. 计算大数加法
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)
}
总结
虽然代码行数看起来也不少，但步骤清晰，其中每一步都很简单，看过一遍之后，你还会忘记吗？这就是问题分解的魅力，大题化小，小题化了，一个问题分解成多个很简单的小问题。
当然，我们也可以将这些函数全部合并到同一个函数里面，如果这样做，不仅代码行数减少了，而且代码中会少很多内存分配的步骤，导致内存占用和运行时间都会减少，但代价是更不容易记忆，这当然算追求极致，但对于以面试为目的同学，记得牢才更重要。
进阶，如何优化运行时间？
上面介绍的算法，便于记忆且写法相对简单，但性能还有很大的提升空间。我们代码中用int64来存储数字，但只用来进行一位数的计算。如果能一次计算多位，就能减少计算次数。
可能有人已经注意到，我在代码中定义了一个base的常量为10，代表每个int64只存储一位数。如果将base改成10000，每个int64就可以存储四位数。但同时，两个convert函数也需要修改，四位四位地转换。
优化后的格式转化函数
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([]int64{d}, 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
}
到底能减少多少时间？
这样依赖，我们可以减少多少次计算呢？
假设两个大数分别有m位和n位，按照原来的算法需要计算m * n 次乘法，以及n次加法，而新的算法只需要(m/4) * (n/4)次乘法和(n/4)次加法，如果只看乘法，计算次数只有原来的1/16！
同时，存储所需的空间也会减少。原来的算法需要为大数分配(m+n)个int64空间，新的算法只需要四分之一。
优化的极限
按照这种思路，最多一组几位数呢？那就要看int64能装下多少了。众所周知，int64能表示的最大整数是2^63-1也就是9223372036854775807，十进制是19位数。但需要注意的是，在我们的算法中会出现两个int64相乘的计算，也就是我们最多只能存9位数，这样两个9位数相乘最多得到18位数，不会超出int64的范围。
于是我们把base改成1e9(10的9次方)，两个convert函数也做相应的修改，就可以得到打败100%网友的代码了。
网友评论