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. // @author 连城 (http://weibo.com/lianchengzju)
  3. // 一个字符对应一个int
  4. // 时间复杂度O(n*m)，空间复杂度O(n+m)
  5. typedef vector bigint;
  7. bigint make_bigint(string const& repr) {
  8.     bigint n;
  9.     transform(repr.rbegin(), repr.rend(), back_inserter(n),
  10.             [](char c) { return c - '0'; });
  11.     return n;
  12. }
  14. string to_string(bigint const& n) {
  15.     string str;
  16.     transform(find_if(n.rbegin(), prev(n.rend()),
  17.             [](char c) { return c > '\0'; }), n.rend(), back_inserter(str),
  18.             [](char c) { return c + '0'; });
  19.     return str;
  20. }
  22. bigint operator*(bigint const& x, bigint const& y) {
  23.     bigint z(x.size() + y.size());
  25.     for (size_t i = 0; i < x.size(); ++i)
  26.         for (size_t j = 0; j < y.size(); ++j) {
  27.             z[i + j] += x[i] * y[j];
  28.             z[i + j + 1] += z[i + j] / 10;
  29.             z[i + j] %= 10;
  30.         }
  32.     return z;
  33. }
  35. class Solution {
  36. public:
  37.     string multiply(string num1, string num2) {
  38.         return to_string(make_bigint(num1) * make_bigint(num2));
  39.     }
  40. };

代码2

  1. // Multiply Strings
  2. // 9个字符对应一个int64_t
  3. // 时间复杂度O(n*m/81)，空间复杂度O((n+m)/9)
  4. /** 大整数类. */
  5. class BigInt {
  6. public:
  7.     /**
  8.      * @brief 构造函数，将字符串转化为大整数.
  9.      * @param[in] s 输入的字符串
  10.      * @return 无
  11.      */
  12.     BigInt(string s) {
  13.         vector<int64_t> result;
  14.         result.reserve(s.size() / RADIX_LEN + 1);
  16.         for (int i = s.size(); i > 0; i -= RADIX_LEN) {  // [i-RADIX_LEN, i)
  17.             int temp = 0;
  18.             const int low = max(i - RADIX_LEN, 0);
  19.             for (int j = low; j < i; j++) {
  20.                 temp = temp * 10 + s[j] - '0';
  21.             }
  22.             result.push_back(temp);
  23.         }
  24.         elems = result;
  25.     }
  26.     /**
  27.      * @brief 将整数转化为字符串.
  28.      * @return 字符串
  29.      */
  30.     string toString() {
  31.         stringstream result;
  32.         bool started = false; // 用于跳过前导0
  33.         for (auto i = elems.rbegin(); i != elems.rend(); i++) {
  34.             if (started) { // 如果多余的0已经都跳过，则输出
  35.                 result << setw(RADIX_LEN) << setfill('0') << *i;
  36.             } else {
  37.                 result << *i;
  38.                 started = true; // 碰到第一个非0的值，就说明多余的0已经都跳过
  39.             }
  40.         }
  42.         if (!started) return "0"; // 当x全为0时
  43.         else return result.str();
  44.     }
  46.     /**
  47.      * @brief 大整数乘法.
  48.      * @param[in] x x
  49.      * @param[in] y y
  50.      * @return 大整数
  51.      */
  52.     static BigInt multiply(const BigInt &x, const BigInt &y) {
  53.         vector<int64_t> z(x.elems.size() + y.elems.size(), 0);
  55.         for (size_t i = 0; i < y.elems.size(); i++) {
  56.             for (size_t j = 0; j < x.elems.size(); j++) { // 用y[i]去乘以x的各位
  57.                 //  两数第i, j位相乘，累加到结果的第i+j位
  58.                 z[i + j] += y.elems[i] * x.elems[j];
  60.                 if (z[i + j] >= BIGINT_RADIX) { //  看是否要进位
  61.                     z[i + j + 1] += z[i + j] / BIGINT_RADIX; //  进位
  62.                     z[i + j] %= BIGINT_RADIX;
  63.                 }
  64.             }
  65.         }
  66.         while (z.back() == 0) z.pop_back();  // 没有进位，去掉最高位的0
  67.         return BigInt(z);
  68.     }
  70. private:
  71.     typedef long long int64_t;
  72.     /** 一个数组元素对应9个十进制位，即数组是亿进制的
  73.      * 因为 1000000000 * 1000000000 没有超过 2^63-1
  74.      */
  75.     const static int BIGINT_RADIX = 1000000000;
  76.     const static int RADIX_LEN = 9;
  77.     /** 万进制整数. */
  78.     vector<int64_t> elems;
  79.     BigInt(const vector<int64_t> num) : elems(num) {}
  80. };
  83. class Solution {
  84. public:
  85.     string multiply(string num1, string num2) {
  86.         BigInt x(num1);
  87.         BigInt y(num2);
  88.         return BigInt::multiply(x, y).toString();
  89.     }
  90. };

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