GuilinDev

Lc0043

05 August 2008

43 - Multiply Strings

原题概述

Given two non-negative integers

1
num1
and
1
num2
represented as strings, return the product of
1
num1
and
1
num2
, also represented as a string.

Example 1:

1
2
Input: num1 = "2", num2 = "3"
Output: "6"

Example 2:

1
2
Input: num1 = "123", num2 = "456"
Output: "56088"

Note:

  1. The length of both
    1
    
    num1
    
    and
    1
    
    num2
    
    is < 110.
  2. Both
    1
    
    num1
    
    and
    1
    
    num2
    
    contain only digits
    1
    
    0-9
    
    .
  3. Both
    1
    
    num1
    
    and
    1
    
    num2
    
    do not contain any leading zero, except the number 0 itself.
  4. You must not use any built-in BigInteger library or convert the inputs to integer directly.

题意和分析

两个字符串表示的数字,相乘后返回字符串表示的乘积(这样可以计算超大数相乘,不受int和long数值范围的约束),就用多位数的乘法过程,每位相乘然后错位相加,把错位相加的结果保存在一个一维数组中,然后每位上算进位,最后每位就变成一位,去掉首位的0,然后把每位数字按顺序保存到结果中。

代码

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
class Solution {
    public String multiply(String num1, String num2) {
        int m = num1.length(), n = num2.length();
        // 二者的乘积最大长度为m + n,例如"5" * "7"
        int[] positions = new int[m + n];
        
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                //这步乘积可能是一位数或两位数
                int product = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
                
                // 在array的基础上加上新得到乘积,找到相应的位置
                // 第一个位置是十位,第二个位置存个位
                int tens = i + j;
                int ones = i + j + 1;
                int sum = product + positions[ones]; // ones是上一次乘积可能存上的tens
                positions[tens] += sum / 10;
                positions[ones] = sum % 10;
            }
        }
        
        StringBuilder sb = new StringBuilder();
        for (int p : positions) {
            // 两个条件一起表示没有乘以0
            if (!(sb.length() == 0 && p == 0)) {
                sb.append(p);
            }
        }
        return sb.length() == 0 ? "0" : sb.toString();
    }
}