43. 字符串相乘：

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。

样例 1：

输入: num1 = "2", num2 = "3"输出: "6"

样例 2：

输入: num1 = "123", num2 = "456"输出: "56088"

提示：

• 1 <= num1.length, num2.length <= 200
• num1 和 num2 只能由数字组成。
• num1 和 num2 都不包含任何前导零，除了数字0本身。

分析：

• 面对这道算法题目，二当家的陷入了沉思。
• 看了题意就是不允许我们直接将输入的两个数转成数字，然后直接用乘法API，那我们就模拟大数乘法就可以了。
• 想起了小学做数学乘法，先学9*9乘法表，之后的乘法都是“分治”为个位数的乘法，再把结果加起来。

题解：

rust

impl Solution {pub fn multiply(num1: String, num2: String) -> String {if num1 == "0" || num2 == "0" {return "0".to_owned();}let (m, n) = (num1.len(), num2.len());let mut ans_arr = vec![0; m + n - 1];num1.as_bytes().iter().enumerate().for_each(|(i1, &c1)| {num2.as_bytes().iter().enumerate().for_each(|(i2, &c2)| {ans_arr[i1 + i2] += ((c1 - b'0') * (c2 - b'0')) as u16;});});let mut carry = 0;let mut ans = Vec::with_capacity(m + n);ans_arr.iter().rev().for_each(|&c| {let mut b = c + carry;carry = b / 10;b %= 10;ans.push(b as u8 + b'0');});if carry > 0 {ans.push(carry as u8 + b'0');}ans.reverse();String::from_utf8(ans).unwrap()}
}

go

func multiply(num1 string, num2 string) string {if num1 == "0" || num2 == "0" {return "0"}m, n := len(num1), len(num2)ansArr := make([]int, m+n)for i1, c1 := range num1 {for i2, c2 := range num2 {ansArr[i1+i2+1] += int(c1-'0') * int(c2-'0')}}for i := m + n - 1; i > 0; i-- {ansArr[i-1] += ansArr[i] / 10ansArr[i] %= 10}ans := ""idx := 0if ansArr[0] == 0 {idx = 1}for ; idx < m+n; idx++ {ans += strconv.Itoa(ansArr[idx])}return ans
}

c++

class Solution {
public:string multiply(string num1, string num2) {if (num1 == "0" || num2 == "0") {return "0";}int m = num1.size(), n = num2.size();auto ansArr = vector<int>(m + n);for (int i = m - 1; i >= 0; --i) {int x = num1.at(i) - '0';for (int j = n - 1; j >= 0; --j) {int y = num2.at(j) - '0';ansArr[i + j + 1] += x * y;}}for (int i = m + n - 1; i > 0; --i) {ansArr[i - 1] += ansArr[i] / 10;ansArr[i] %= 10;}int index = ansArr[0] == 0 ? 1 : 0;string ans;while (index < m + n) {ans.push_back(ansArr[index] + '0');index++;}return ans;}
};

c

char * multiply(char * num1, char * num2){int m = strlen(num1), n = strlen(num2);char *ans = malloc(sizeof(char) * (m + n + 3));memset(ans, 0, sizeof(char) * (m + n + 3));if ((m == 1 && num1[0] == '0') || (n == 1 && num2[0] == '0')) {ans[0] = '0', ans[1] = 0;return ans;}int *ansArr = malloc(sizeof(int) * (m + n + 3));memset(ansArr, 0, sizeof(int) * (m + n + 3));for (int i = m - 1; i >= 0; --i) {int x = num1[i] - '0';for (int j = n - 1; j >= 0; --j) {int y = num2[j] - '0';ansArr[i + j + 1] += x * y;}}for (int i = m + n - 1; i > 0; --i) {ansArr[i - 1] += ansArr[i] / 10;ansArr[i] %= 10;}int index = ansArr[0] == 0 ? 1 : 0;int ansLen = 0;while (index < m + n) {ans[ansLen++] = ansArr[index] + '0';++index;}return ans;
}

python

class Solution:def multiply(self, num1: str, num2: str) -> str:if num1 == "0" or num2 == "0":return "0"m, n = len(num1), len(num2)ans_arr = [0] * (m + n)for i in range(m - 1, -1, -1):x = int(num1[i])for j in range(n - 1, -1, -1):ans_arr[i + j + 1] += x * int(num2[j])for i in range(m + n - 1, 0, -1):ans_arr[i - 1] += ans_arr[i] // 10ans_arr[i] %= 10index = 1 if ans_arr[0] == 0 else 0ans = "".join(str(x) for x in ans_arr[index:])return ans

java

class Solution {public String multiply(String num1, String num2) {if ("0".equals(num1) || "0".equals(num2)) {return "0";}int   m      = num1.length(), n = num2.length();int[] ansArr = new int[m + n - 1];for (int i = m - 1; i >= 0; --i) {int x = num1.charAt(i) - '0';for (int j = n - 1; j >= 0; --j) {int y = num2.charAt(j) - '0';ansArr[i + j] += x * y;}}StringBuilder ans   = new StringBuilder();int           carry = 0;for (int i = m + n - 2; i >= 0; --i) {int b = ansArr[i] + carry;carry = b / 10;b %= 10;ans.append(b);}if (carry > 0) {ans.append(carry);}return ans.reverse().toString();}
}

非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://le-yi.blog.csdn.net/ 博客原创~