题目描述
以字符串的形式读入两个数字，编写一个函数计算它们的乘积，以字符串形式返回。
（字符串长度不大于10000，保证字符串仅由'0'~'9'这10种字符组成）
方法一： 模拟
解题思路
用代码模拟2个数相乘的过程即可。整体的流程就是：把 num2 从右往左遍历，每一个数字和 num1 进行相乘， 最后把每次相乘的结果相加就得到答案。
需要注意的是每次相乘的时候，因为有可能数字非常大，超出了整型、长整型的表示范围，所以每次相乘的时候仍然需要用 字符串的形式保存结果，把每次相乘的结果相加，仍然也是 2 个字符串相加。
在写代码的过程中，注意下进位的问题及反转的问题就可以。
这里以 12 * 99 为例， 大体流程思路如下图所示：
复杂度分析
时间复杂度： O(N * M + M * max(N, M))，N 为 num1 的长度， M 为 num2 的长度。
需要遍历 num2 的每个数字，每个数字还需要和 num2 的每个数字进行相乘，所以这里复杂度为 O(N*M)。
在每次相乘结果相加的时候，也仍然需要遍历每个数字进行相加，这里遍历的次数就看 num1 和 num2 哪个字符串更长，即时间复杂度为 O(max(N, M))。
而整个过程在外面大的循环里，即 num2 的遍历循环里，所以这里复杂度为 O(M*max(N, M))。所以，最后总的时间复杂度为 O(N * M + M * max(N, M))
空间复杂度： O(N + M)，N 为 num1 的长度， M 为 num2 的长度。
num1 和 num2 相乘的结果的最长长度为 N + M , 最长不会超过它，所以空间复杂度为 O(N + M)
示例代码
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param num1 string字符串 第一个整数
* @param num2 string字符串 第二个整数
* @return string字符串
*/
public String solve (String num1, String num2) {
// 判断不合法的输入
if (num1 == null || num1.length() == 0 || num2 == null || num2.length() == 0) {
return null;
}
// 如果 num1 或 num2 其中有一个为 0， 则最后相乘的结果为 0
if ("0".equals(num1) || "0".equals(num2)) {
return "0";
}
char[] chars1 = num1.toCharArray();
char[] chars2 = num2.toCharArray();
// 最后的结果
String res = "0";
// 相乘之后，后面需要补零的个数
int zero = 0;
// 从右往左遍历 num2 字符串中的每一个数字， 使其和 num1 字符串相乘， 再相加，即得最后结果
for (int i = chars2.length - 1; i >= 0; i--) {
// 每一个数字和 num1 字符串相乘的结果
StringBuilder temp = new StringBuilder();
// 保存进位
int carry = 0;
// 将后面需要的零补齐
for (int j = 0; j < zero; j++) {
temp.append('0');
}
zero++;
// 取出 num2 字符串的每一个数字， 记为 y
int y = chars2[i] - '0';
// 使 y 和 num1 字符串相乘
for (int j = chars1.length - 1; j >= 0; j--) {
int x = chars1[j] - '0';
int num = x * y + carry;
temp.append(num % 10);
carry = num / 10;
}
// 如果最后进位不为 0 ， 则还需要往前进 carry 位
if (carry != 0) {
temp.append(carry);
}
// 把每次相乘的结果相加起来，就是最后的结果
res = bigNumberAdd(res, temp.reverse().toString());
}
return res;
}
/**
*
* @param num1 第一个数字字符串
* @param num2 第二个数字字符串
* @return 两个字符串相加之后的结果
*/
public String bigNumberAdd(String num1, String num2) {
// 判断不合法输入
if (num1 == null || num1.length() == 0 || num2 == null || num2.length() == 0) {
return null;
}
// num1 字符串的下标， 从右往左遍历
int index1 = num1.length() - 1;
// num2 字符串的下标， 从右往左遍历
int index2 = num2.length() - 1;
// 最后相加的结果
StringBuilder res = new StringBuilder();
// 保存进位
int carry = 0;
// num1 或 num2 只要有一个字符串还有值，就继续循环
while (index1 >= 0 || index2 >= 0) {
// 拿到 num1 的一个数字
int x = index1 >= 0 ? num1.charAt(index1--) - '0' : 0;
// 拿到 num2 的一个数字
int y = index2 >= 0 ? num2.charAt(index2--) - '0' : 0;
// 拿到的 2 个数字相加，要考虑进位的情况
int num = x + y + carry;
// 该位只保存个位数
res.append(num % 10);
// 十位数要往前进一位
carry = num / 10;
}
// 如果最后进位不为 0 ， 则还需要往前进 carry 位
if (carry != 0) {
res.append(carry);
}
return res.reverse().toString();
}
} 方法二： 优化方法一
解题思路
方法一就是平常我们做乘法的步骤，先相乘，再相加。
优化之后就是直接算乘法，把 num1 的每一位数字 和 num2 的每一位数字相乘， 相乘的结果放到对应的位置上，最后我们再处理相乘之后的结果即可。
如果 num1 的长度为 N ， num2 的长度为 M， 则 num1 * num2 的结果最长长度为 N + M，所以开辟一个长度为 N + M 的整型数组来操作相乘的结果。
但有时候长度没有达到 N+M ， 所以这里需要判断一下有没有前置零的影响，这块具体思路请参照代码。
这里以 12 * 99 为例， 大体流程如下图所示：
得到了 num 数组，之后的操作就是每个位置只保留一位数字，即处理进位：
复杂度分析
时间复杂度： O(N*M)，N 为 num1 的长度， M 为 num2 的长度。
代码里有 2 层嵌套的 for 循环， 就是把 num1 的每一个数字 和 num2 的每一个数字相乘的消耗。
空间复杂度：O(N+M)，N 为 num1 的长度， M 为 num2 的长度。
需要开辟一个长度为 N + M 的整型数组来操作相乘之后的结果。
示例代码
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param num1 string字符串 第一个整数
* @param num2 string字符串 第二个整数
* @return string字符串
*/
public String solve(String num1, String num2) {
// 判断不合法的输入
if (num1 == null || num1.length() == 0 || num2 == null || num2.length() == 0) {
return null;
}
// 如果有一个字符串为 0 ，结果就是 0
if ("0".equals(num1) || "0".equals(num2)) {
return "0";
}
// 最后相乘的结果，长度最多就是 2 个字符串的长度相加
int[] num = new int[num1.length() + num2.length()];
// num1 的每一个数字， 和 num2 的每一个数字相乘； 放到 num 数组的对应位置上
for (int i = num1.length() - 1; i >= 0; i--) {
for (int j = num2.length() - 1; j >= 0; j--) {
// 同一个位置可能有多种情况映射过来， 所以结果位置上的结果取个累加和即可
num[i + j + 1] += (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
}
}
// 如果最后的结果有进位，那么 num 数组的第一位数不为零；
// 如果没进位，则为零。这种情况需要注意不要这个零。
int end = num[0] == 0 ? 1 : 0;
StringBuilder res = new StringBuilder();
// 保存进位的值
int carry = 0;
// 从后往前遍历 num 数组，最后的结果有进位则遍历到 0 结束，没进位就遍历到 1 结束。
for (int i = num.length - 1; i >= end; i--) {
// 数组上对应位置的数 和 进位相加的结果
int temp = num[i] + carry;
// temp的个位数，才是属于对应位置上的数
res.append(temp % 10);
// temp的十位数，是属于对应位置的前一个位置上的数，即是进位的值
carry = temp / 10;
}
// 最后的进位不为零，也是计算的结果，往前进 carry 位即可。
if (carry != 0) {
res.append(carry);
}
// 根据上述的流程，把 res 倒序一下，就是最后 2 个字符串相乘的结果
return res.reverse().toString();
}
} 
京公网安备 11010502036488号