题目描述
给定两个以字符串形式表示的非负整数 num1 和 num2,返回 num1 和 num2 的乘积,它们的乘积也表示为字符串形式。
样例
示例 1:
输入: num1 = "2", num2 = "3"
输出: "6"
示例 2:
输入: num1 = "123", num2 = "456"
输出: "56088"
算法1
(暴力枚举) $O(N * M)$
竖式运算思想,以 num1 为 123,num2 为 456 为例分析:
遍历 num2 每一位与 num1 进行相乘,将每一步的结果进行累加。
注意:
num2 除了第一位的其他位与 num1 运算的结果需要 补0.
字符串相加不需要补0,相同位置直接相加 + 上一次相加的结果的进位
时间复杂度
O(NM)
参考文献
Java 代码
class Solution {
public String multiply(String num1, String num2) {
if(num1.length() == 0){
return num2;
}
if(num2.length() == 0){
return num1;
}
int n = num1.length()-1,m = num2.length()-1;
String res = "0";
for(int i = m; i >= 0; i--){
StringBuffer sb = new StringBuffer();
int carry = 0;
int numm = num2.charAt(i) - '0';
//补0
for(int j = 0; j < m - i; i++){
sb.append(0);
}
for(int j = n; j >= 0 || carry != 0; j--){
int numn = j < 0? 0 : num1.charAt(j) - '0';
int result = numm * numn + carry;
sb.append(result % 10);
carry = result / 10;
}
res = addString(res,sb.reverse().toString());
}
return res;
}
public String addString(String str1,String str2){
int carry = 0;
StringBuffer sb = new StringBuffer();
for(int i = str1.length()-1,j = str2.length() - 1;
i >= 0 || j >= 0 || carry != 0; i--,j--){
int n = i < 0? 0 : str1.charAt(i) - '0';
int m = j < 0? 0 : str2.charAt(j) - '0';
int result = n + m + carry;
sb.append(result % 10);
carry = result / 10;
}
return sb.reverse().toString();
}
}
算法2
(暴力枚举 + 空间优化) $O(N * M)$
上面那种操作因为字符串的操作太多了,浪费了很多空间,并且还需要一些补0 的操作,整体空间复杂度:O(N + M)
优化:
该算法是通过两数相乘时,乘数某位与被乘数某位相乘,与产生结果的位置的规律来完成。具体规律如下:
乘数 num1 位数为 MMM,被乘数 num2 位数为 NNN, num1 x num2 结果 res 最大总位数为 M+N
num1[i] x num2[j] 的结果为 tmp,其第一位位于 res[i+j],第二位位于 res[i+j+1]。
时间复杂度
O(NM)
参考文献
Java 代码
public String multiply(String num1, String num2) {
int n = num1.length();
int m = num2.length();
if(n == 0 || m == 0){
return "0";
}
if(num1.charAt(0) == '0' || num2.charAt(0) == '0') return "0";
int[] res = new int[n + m];
for(int i = n - 1; i >= 0; i--){
for(int j = m - 1; j >= 0; j--){
int sum = res[i + j + 1] + (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
res[i + j + 1] = sum % 10;
res[i + j] += sum / 10;
}
}
StringBuffer sb = new StringBuffer();
for(int i = 0; i < res.length; i++){
if(i == 0 && res[i] == 0) continue;
sb.append(res[i]);
}
return sb.toString();
}