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.

分析

高精度乘法。

常见的做法是将字符转化为一个int，一一对应，形成一个int数组。但是这样很浪费空间，一个int32的最大值是2^{31}-1=2147483647，可以与9个字符对应，由于有乘法，减半，则至少可以与4个字符一一对应。一个int64可以与9个字符对应。

代码1

  1. // Multiply Strings
  2. // 一个字符对应一个int
  3. // 时间复杂度O(n*m)，空间复杂度O(n+m)
  4. public class Solution {
  5.     public String multiply(String num1, String num2) {
  6.         BigInt bigInt1 = new BigInt(num1);
  7.         BigInt bigInt2 = new BigInt(num2);
  8.         BigInt result = BigInt.multiply(bigInt1, bigInt2);
  9.         return result.toString();
  10.     }
  12.     // 一个字符对应一个int
  13.     static class BigInt {
  14.         private final int[] d;
  16.         public BigInt(String s) {
  17.             this.d = fromString(s);
  18.         }
  19.         public BigInt(int[] d) {
  20.             this.d = d;
  21.         }
  23.         private static int[] fromString(String s) {
  24.             int[] d = new int[s.length()];
  25.             for (int i = s.length() - 1, j = 0; i >= 0; --i)
  26.                 d[j++] = Character.getNumericValue(s.charAt(i));
  27.             return d;
  28.         }
  30.         @Override
  31.         public String toString() {
  32.             final StringBuilder sb = new StringBuilder();
  33.             for (int i = d.length - 1; i >= 0; --i) {
  34.                 sb.append(Character.forDigit(d[i], 10));
  35.             }
  36.             return sb.toString();
  37.         }
  39.         public static BigInt multiply(BigInt x, BigInt y) {
  40.             int[] z = new int[x.d.length + y.d.length];
  41.             for (int i = 0; i < x.d.length; ++i) {
  42.                 for (int j = 0; j < y.d.length; ++j) {
  43.                     z[i + j] += x.d[i] * y.d[j];
  44.                     z[i + j + 1] += z[i + j] / 10;
  45.                     z[i + j] %= 10;
  46.                 }
  47.             }
  48.             // find the first 0 from right to left
  49.             int i = z.length - 1;
  50.             for (; i > 0 && z[i] == 0; --i) /* empty */;
  52.             if (i == z.length - 1) {
  53.                 return new BigInt(z);
  54.             } else { // make a copy
  55.                 int[] tmp = new int[i + 1];
  56.                 System.arraycopy(z, 0, tmp, 0, i + 1);
  57.                 return new BigInt(tmp);
  58.             }
  59.         }
  60.     }
  61. }

代码2

  1. // Multiply Strings
  2. // 9个字符对应一个 long
  3. // 时间复杂度O(n*m)，空间复杂度O(n+m)
  4. public class Solution {
  5.     public String multiply(String num1, String num2) {
  6.         BigInt bigInt1 = BigInt.fromString(num1);
  7.         BigInt bigInt2 = BigInt.fromString(num2);
  8.         BigInt result = BigInt.multiply(bigInt1, bigInt2);
  9.         return result.toString();
  10.     }
  12.     // 9个字符对应一个 long
  13.     static class BigInt {
  14.         /** 一个数组元素对应9个十进制位，即数组是亿进制的
  15.          * 因为 1000000000 * 1000000000 没有超过 2^63-1
  16.          */
  17.         final static int BIGINT_RADIX = 1000000000;
  18.         final static int RADIX_LEN = 9;
  19.         /** 万进制整数. */
  20.         private final long[] digits;
  22.         public BigInt(long[] digits) {
  23.             this.digits = digits;
  24.         }
  26.         private static BigInt fromString(String s) {
  27.             long[] digits;
  28.             if (s.length() % RADIX_LEN == 0) {
  29.                 digits = new long[s.length() / RADIX_LEN];
  30.             } else {
  31.                 digits = new long[s.length() / RADIX_LEN + 1];
  32.             }
  33.             for (int i = s.length(), k = 0; i > 0; i -= RADIX_LEN) {
  34.                 long tmp = 0;
  35.                 for (int j = Math.max(0, i - RADIX_LEN); j < i; ++j) {
  36.                     tmp = tmp * 10 + Character.getNumericValue(s.charAt(j));
  37.                 }
  38.                 digits[k++] = tmp;
  39.             }
  40.             return new BigInt(digits);
  41.         }
  43.         @Override
  44.         public String toString() {
  45.             final StringBuilder sb = new StringBuilder(
  46.                     Long.toString(digits[digits.length-1]));
  48.             for (int i = digits.length - 2; i >= 0; --i) {
  49.                 sb.append(String.format("%0" + RADIX_LEN + "d", digits[i]));
  50.             }
  51.             return sb.toString();
  52.         }
  54.         public static BigInt multiply(BigInt x, BigInt y) {
  55.             long[] z = new long[x.digits.length + y.digits.length];
  56.             for (int i = 0; i < x.digits.length; ++i) {
  57.                 for (int j = 0; j < y.digits.length; ++j) {
  58.                     z[i + j] += x.digits[i] * y.digits[j];
  59.                     z[i + j + 1] += z[i + j] / BIGINT_RADIX;
  60.                     z[i + j] %= BIGINT_RADIX;
  61.                 }
  62.             }
  63.             // find the first 0 from right to left
  64.             int i = z.length - 1;
  65.             for (; i > 0 && z[i] == 0; --i) /* empty */;
  67.             if (i == z.length - 1) {
  68.                 return new BigInt(z);
  69.             } else { // make a copy
  70.                 long[] tmp = new long[i + 1];
  71.                 System.arraycopy(z, 0, tmp, 0, i + 1);
  72.                 return new BigInt(tmp);
  73.             }
  74.         }
  75.     }
  76. }

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/simulation/multiply-strings.html