Golang 解大整数乘法

Golang 解大整数乘法

在初学 C 语言的时候，我们一定接触过“字符串相加”或“字符串相乘”之类的问题，对于初学者而言，这类问题的难度一般来说是比较大的（回想起我大一刚刚学习 C 语言时，解决这两道题的过程非常的痛苦）。

今天我们学习如何使用 Golang 来解决大整数乘法问题，即“字符串相乘”问题。

问题描述：LeetCode 43. 字符串相乘

思路

我们将num1视为乘数，num2视为被乘数，字符串相乘的基本思路就是每一次取num2当中的一位数字，与整个num1进行相乘，假定num1的长度是m，而num2的长度是n，那么num2中的n个数就需要与num1进行m * n次相乘。

由于我们进行的是乘法，从num2的最后一位开始与num1进行相乘，当进行到倒数第二位的时候，需要将整个相乘的结果向左移动一位，右侧添加一个0，毕竟在竖式乘法当中就是这样做的。

最后将每一次相乘得到的结果通过“字符串加法”汇总起来，就可以得到最终“字符串乘法”的结果。

总的来说，这道题目的综合性非常的强，既考察了在 Golang 当中如何将字符串与数字进行相互转换，又考察了“字符串乘法”解题模拟的复杂思路。

Golang 代码

func multiply(num1 string, num2 string) string {// 大整数乘法// num1 是乘数, num2 是被乘数if num1 == "0" || num2 == "0" {return "0"}m, n := len(num1), len(num2)ans := ""for i := n - 1; i >= 0; i -- {// 使用被乘数的每一位与乘数相乘, 然后将每一次乘法得到的结果通过"字符串加法"加在一起curr := ""for j := n - 1; j > i; j -- {curr += "0"}// ⬆️ 每进行一次乘法之后, 与模拟竖式乘法类似, 这一次乘数当中数字与被乘数相乘的结果需要补零y := int(num2[i] - '0')cnt := 0    // 记录进位for j := m - 1; j >= 0; j -- {x := int(num1[j] - '0')product := x * y + cntcurr = strconv.Itoa(product % 10) + currcnt = product / 10}for cnt > 0 {curr = strconv.Itoa(cnt % 10) + currcnt /= 10}ans = addStrings(ans, curr)}return ans
} func addStrings(num1, num2 string) string {m, n := len(num1), len(num2)ans := ""cnt := 0for i, j := m - 1, n - 1; i >= 0 || j >= 0; i, j = i - 1, j - 1 {x, y := 0, 0if i >= 0 {x = int(num1[i] - '0')}if j >= 0 {y = int(num2[j] - '0')}curr := x + y + cntans = strconv.Itoa(curr % 10) + anscnt = curr / 10}for cnt > 0 {ans = strconv.Itoa(cnt % 10) + anscnt /= 10}return ans
}