长大后想做什么?做回小孩!

0%

LeetCode——字符串相乘

NO.43 字符串相乘 中等

10uteS.png

思路一:竖式法 想一想竖式是怎么一步一步进行的,模拟这个过程。两个步骤:

  1. 逆序(从低位向高位)遍历乘数num2的每个元素,依次与num1相乘。这个过程中需要注意除了num2的第一个元素(个位数)其他元素都需要在低位补充相应数量的0。每次相乘的结果temp是逆序的。
  2. 将num2的每个元素与num1相乘得到的结果temp和ans相加,此时是顺序遍历两个参数。

遍历结束之后返回逆序结果的翻转。

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
public String multiply(String num1, String num2) {
if (num1==null||num2==null||num1.equals("0")||num2.equals("0")||num1.equals("")||num2.equals(""))return "0";
StringBuilder ans=new StringBuilder();
//遍历num2的每个元素
for (int i=0;i<num2.length();i++){
int x = num2.charAt(num2.length()-i-1)-'0',carry=0;
StringBuilder temp=new StringBuilder();
//除了第一次个位数,其他位需要在低位补相应数量的0
for (int k=0;k<i;k++)temp.append(0);
//依次与num1的每个元素相乘
for (int j=0;j<num1.length();j++){
int y = num1.charAt(num1.length()-j-1)-'0';
//注意加上进位值
int sum=x*y+carry;
carry=sum/10;
temp.append(sum%10);
}
//注意检查进位值,不要遗漏
if (carry>0)temp.append(carry);
//将每位上的乘法结果和ans相加
ans=sum(ans,temp);
}
//最后需要将ans翻转,变成正确顺序
return ans.reverse().toString();
}
//将两个字符串相加
private StringBuilder sum(StringBuilder num1, StringBuilder num2) {
StringBuilder ans=new StringBuilder();
int carry=0,len=Math.max(num1.length(),num2.length());
for (int i=0;i<len;i++){
//两个字符串长度不相等的时候,短的那个在高位补0
int x=i<num1.length()?num1.charAt(i)-'0':0;
int y=i<num2.length()?num2.charAt(i)-'0':0;
//注意加上进位
int sum=x+y+carry;
carry=sum/10;
ans.append(sum%10);
}
//循环结束也要检查进位,防止遗漏
if (carry>0)ans.append(carry);
return ans;
}

时间复杂度:O(MN)

思路二:优化竖式法 该算法是通过两数相乘时,乘数某位与被乘数某位相乘,与产生结果的位置的规律来完成。具体规律如下:

  1. 乘数 num1 位数为 MM,被乘数 num2 位数为 NN, num1 x num2 结果 res 最大总位数为 M+N。
  2. num1[i] x num2[j] 的结果为 tmp(位数为两位,”0x”,”xy”的形式),其第一位位于 res[i+j],第二位位于 res[i+j+1]。

166SQe.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public String multiply(String num1, String num2) {
if (num1==null||num2==null||num1.equals("0")||num2.equals("0")||num1.equals("")||num2.equals(""))return "0";
//两数相乘积最多为M+N位
int[] res=new int[num1.length()+num2.length()];
for (int i=num1.length()-1;i>=0;i--){
int x = num1.charAt(i) - '0';
for (int j=num2.length()-1;j>=0;j--){
int y = num2.charAt(j) - '0';
int sum=x*y+res[i+j+1];
res[i+j+1]=sum%10;
res[i+j]+=sum/10;
}
}
StringBuilder ans=new StringBuilder();
for (int i = 0; i < res.length; i++) {
//积的最高位可能为零,省去不要
if (i==0&&res[0]==0)continue;
ans.append(res[i]);
}
return ans.toString();
}

时间复杂度:O(MN)


本人菜鸟,有错误请告知,感激不尽!

更多题解和学习记录博客:博客github