跳到主要内容

Multiply Strings

描述

Given two numbers represented as strings, return multiplication of the numbers as a string.

Note: The numbers can be arbitrarily large and are non-negative.

分析

高精度乘法。

代码

模拟乘法

// Multiply Strings
// Time Complexity: O(n*m), Space Complexity: O(n+m)
class Solution {
public String multiply(String num1, String num2) {
int m = num1.length(), n = num2.length();
int[] z = new int[m + n];

for(int i = m - 1; i >= 0; i--) {
for(int j = n - 1; j >= 0; j--) {
int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
int sum = mul + z[i+j+1];
z[i + j + 1] = sum % 10;
z[i + j] += sum / 10; // carry
}
}

StringBuilder sb = new StringBuilder();
for(int x : z) {
if(!(sb.length() == 0 && x == 0)) // skip prefix zeros
sb.append(x);
}
return sb.length() == 0 ? "0" : sb.toString();
}
}

转化成整数数组,一个字符对应一个整数

常见的做法是把每个字符转化为一个 int,一一对应,形成一个 int 数组。

// Multiply Strings
// 一个字符对应一个int
// 时间复杂度O(n*m),空间复杂度O(n+m)
public class Solution {
public String multiply(String num1, String num2) {
BigInt bigInt1 = new BigInt(num1);
BigInt bigInt2 = new BigInt(num2);
BigInt result = BigInt.multiply(bigInt1, bigInt2);
return result.toString();
}

// 一个字符对应一个int
static class BigInt {
private final int[] d;

public BigInt(String s) {
this.d = fromString(s);
}
public BigInt(int[] d) {
this.d = d;
}

private static int[] fromString(String s) {
int[] d = new int[s.length()];
for (int i = s.length() - 1, j = 0; i >= 0; --i)
d[j++] = Character.getNumericValue(s.charAt(i));
return d;
}

@Override
public String toString() {
final StringBuilder sb = new StringBuilder();
for (int i = d.length - 1; i >= 0; --i) {
sb.append(Character.forDigit(d[i], 10));
}
return sb.toString();
}

public static BigInt multiply(BigInt x, BigInt y) {
int[] z = new int[x.d.length + y.d.length];
for (int i = 0; i < x.d.length; ++i) {
for (int j = 0; j < y.d.length; ++j) {
z[i + j] += x.d[i] * y.d[j];
z[i + j + 1] += z[i + j] / 10;
z[i + j] %= 10;
}
}
// find the first 0 from right to left
int i = z.length - 1;
for (; i > 0 && z[i] == 0; --i) /* empty */;

if (i == z.length - 1) {
return new BigInt(z);
} else { // make a copy
int[] tmp = new int[i + 1];
System.arraycopy(z, 0, tmp, 0, i + 1);
return new BigInt(tmp);
}
}
}
}

转化成整数数组,9 个字符对应一个 64 位整数

一个字符用一个 int 表示,其实是比较浪费内存空间的,因为一个 int64 的最大值是2631=92233720368547758072^{63}-1=9223372036854775807,可以与 19 个字符对应,由于有乘法,减半,则至少可以与 9 个字符一一对应。

// Multiply Strings
// 9个字符对应一个 long
// 时间复杂度O(n*m),空间复杂度O(n+m)
public class Solution {
public String multiply(String num1, String num2) {
BigInt bigInt1 = BigInt.fromString(num1);
BigInt bigInt2 = BigInt.fromString(num2);
BigInt result = BigInt.multiply(bigInt1, bigInt2);
return result.toString();
}

// 9个字符对应一个 long
static class BigInt {
/** 一个数组元素对应9个十进制位,即数组是亿进制的
* 因为 1000000000 * 1000000000 没有超过 2^63-1
*/
final static int BIGINT_RADIX = 1000000000;
final static int RADIX_LEN = 9;
/** 万进制整数. */
private final long[] digits;

public BigInt(long[] digits) {
this.digits = digits;
}

private static BigInt fromString(String s) {
long[] digits;
if (s.length() % RADIX_LEN == 0) {
digits = new long[s.length() / RADIX_LEN];
} else {
digits = new long[s.length() / RADIX_LEN + 1];
}
for (int i = s.length(), k = 0; i > 0; i -= RADIX_LEN) {
long tmp = 0;
for (int j = Math.max(0, i - RADIX_LEN); j < i; ++j) {
tmp = tmp * 10 + Character.getNumericValue(s.charAt(j));
}
digits[k++] = tmp;
}
return new BigInt(digits);
}

@Override
public String toString() {
final StringBuilder sb = new StringBuilder(
Long.toString(digits[digits.length-1]));

for (int i = digits.length - 2; i >= 0; --i) {
sb.append(String.format("%0" + RADIX_LEN + "d", digits[i]));
}
return sb.toString();
}

public static BigInt multiply(BigInt x, BigInt y) {
long[] z = new long[x.digits.length + y.digits.length];
for (int i = 0; i < x.digits.length; ++i) {
for (int j = 0; j < y.digits.length; ++j) {
z[i + j] += x.digits[i] * y.digits[j];
z[i + j + 1] += z[i + j] / BIGINT_RADIX;
z[i + j] %= BIGINT_RADIX;
}
}
// find the first 0 from right to left
int i = z.length - 1;
for (; i > 0 && z[i] == 0; --i) /* empty */;

if (i == z.length - 1) {
return new BigInt(z);
} else { // make a copy
long[] tmp = new long[i + 1];
System.arraycopy(z, 0, tmp, 0, i + 1);
return new BigInt(tmp);
}
}
}
}

相关题目