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. 位数分别为 i 和 j 的两个数相乘，乘积的位数不超过 i+j 位。
  2. 把结果看作一个大小为 i+j 的数组，那么第一个数的第 i 位和第二个数的第 j 位的乘积会影响结果的第 i+j 位和第 i+j+1 位。

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