LeetCode43.字符串相乘【大整数相乘】

文章目录

• • 📜题目描述
  • 💡解题思路

📜题目描述

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

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

示例1

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

示例1

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

提示：

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

💡解题思路

解法1

代码1

对于解法1来说，时间复杂度：O(MN+N^2)

M为num1的长度，N为num2的长度

外层：N , 内层：遍历num1：M，字符串相加（最大为M+N)

​ 内层整体取M+N

所以整体是M*N+N^2

解法2

该算法是通过两数相乘时，乘数某位与被乘数某位相乘，与产生结果的位置的规律来完成

乘数num1的长度为M，num2的长度为N

那么他们的结果的位数不会超过M+N（一位数*两位数结果最大也就3位数 99*9），假设存放在串mul中

对于串num1，和串num2，num1[i]*num2[j]的结果一定是两位数并且小于等于81，"xy"形式或者"0y形式"，其中第一位位于mul[i+j],第二位位于mul[i+j+1]

如图所示：

所以，思路就是：

1. 首先new一个M+N大小的int数组mul用于存放最后结果
2. 然后依次把num1[i]与num2[j]相乘的结果 追加到 mul[i+j+1]位置，然后让mul[i+j]位置 += mul[i+j+1]%10 , mul[i+j+1]位置/=10

最后的整型数组用一个string依次拼接就是目标结果
代码2