LeetCode 43. Multiply Strings [Medium]

题目来源:https://leetcode.com/problems/multiply-strings/

题目难度:Medium

解答1[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
import java.util.Scanner;
public class Main {
public String multiply(String num1, String num2) {
int n1 = num1.length(), n2 = num2.length();
int[] products = new int[n1 + n2];
for (int i = n1 - 1; i >= 0; i--) {
for (int j = n2 - 1; j >= 0; j--) {
int d1 = num1.charAt(i) - '0';
int d2 = num2.charAt(j) - '0';
products[i + j + 1] += d1 * d2;
}
}
int carry = 0;
for (int i = products.length - 1; i >= 0; i--) {
int tmp = (products[i] + carry) % 10;
carry = (products[i] + carry) / 10;
products[i] = tmp;
}
StringBuilder sb = new StringBuilder();
for (int num : products)
sb.append(num);
while (sb.length() != 0 && sb.charAt(0) == '0')
sb.deleteCharAt(0);
return sb.length() == 0 ? "0" : sb.toString();
}
}

这个算法基于一下规律:

  1. 位数分别为 ij 的两个数相乘,乘积的位数不超过 i+j 位。
  2. 把结果看作一个大小为 i+j 的数组,那么第一个数的第 i 位和第二个数的第 j 位的乘积会影响结果的第 i+j 位和第 i+j+1 位。

因此,把第一个数的第 i 位和第二个数的第 j 位的乘积先存到结果的 i+j+1 位,最后再统一计算进位。