Leetcode之43-字符串相乘(Multiply Strings)

算法题

题干

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

示例

1
2
3
4
5
6
7
示例 1:
输入: num1 = "2", num2 = "3"
输出: "6"

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

说明

  1. num1和num2的长度小于110。
  2. num1和num2只包含数字0-9。
  3. num1和num2均不以零开头, 除非是数字0本身。
  4. 不能使用任何标准库的大数类型(比如BigInteger)或直接将输入转换为整数来处理。

思路

这道题本身不难, 只要按照我们平时计算乘法的步骤来操作就好。
背景: 两个数字a和b相乘, 假设数字a和b的位数分别为m和n, 那么相乘结果c的位数肯定不会超过m+n。
前提: 数字a和b从左到右位数索引位置从0开始,分别为0~m-1和0~n-1
结论: 数字a的第i位数字和数字b的第j位数字相乘的结果肯定位于结果c的第i+j+1索引处。

举例

我们以123*456为例来看具体的乘法步骤。

结果索引值 0 1 2 3 4 5
数字a 1 2 3
数字b 4 5 6
a*b个位数 6 12 18
a*b十位数 5 10 15
a*b百位数 4 8 12
未进位和 4 13 28 27 18
最终结果 5 6 0 8 8

说明: 表格中的最终结果是通过未进位和从右到左依次进位得到的。

Java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public static String multiply(String num1, String num2) {
final int num1Len = num1.length(), num2Len = num2.length();
int[] multiply = new int[num1Len + num2Len];
for (int i = num1Len - 1; i >= 0; i--) {
for (int j = num2Len - 1; j >= 0; j--) {
multiply[i + j + 1] += (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
}
}
int carry = 0;
for (int k = num1Len + num2Len - 1; k >= 0; k--) {
int sum = multiply[k] + carry;
multiply[k] = sum % 10;
carry = sum / 10;
}
StringBuilder data = new StringBuilder(16);
int firstNotZeroIndex = 0;
while (firstNotZeroIndex <= num1Len + num2Len - 1 && multiply[firstNotZeroIndex] == 0) {
firstNotZeroIndex++;
}
if (firstNotZeroIndex == num1Len + num2Len) {
return "0";
}
for (int i = firstNotZeroIndex; i <= num1Len + num2Len - 1; i++) {
data.append(multiply[i]);
}
return data.toString().trim();
}

代码解析

  1. 第4-7行代码表示具体的乘法过程, 将每位相乘的结果存储在目标数组中。
  2. 第10-14行代码表示对未进位和进行进位, 如表格最后两行。
  3. 第17-19行代码表示找第一个不是0的位置, 除非数字0, 其余数字均不能以0开头。
  4. 第20-22行代码表示所有未进位和全是0, 换句话说就是方法入参当中至少有一个为0。
如果有任何错误或疑问, 欢迎小伙伴们评论区留言^-^
( 完 )

欢迎各位看官关注

麻辣烫,走起
0%