算法精粹(algorithm-essentials)

感谢soulmachine@github提供内容
## 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

{% codesnippet "./code/multiply-strings-1."+book.suffix, language=book.suffix %}{% endcodesnippet %}


### 代码2

{% if book.java %}
{% codesnippet "./code/multiply-strings-2."+book.suffix, language=book.suffix %}{% endcodesnippet %}
{% endif %}

{% if book.cpp %}
```cpp
// Multiply Strings
// 9个字符对应一个int64_t
// 时间复杂度O(n*m/81),空间复杂度O((n+m)/9)
/** 大整数类. */
class BigInt {
public:
/**
* @brief 构造函数,将字符串转化为大整数.
* @param[in] s 输入的字符串
* @return 无
*/
BigInt(string s) {
vector result;
result.reserve(s.size() / RADIX_LEN + 1);

for (int i = s.size(); i > 0; i -= RADIX_LEN) { // [i-RADIX_LEN, i)
int temp = 0;
const int low = max(i - RADIX_LEN, 0);
for (int j = low; j < i; j++) {
temp = temp * 10 + s[j] - '0';
}
result.push_back(temp);
}
elems = result;
}
/**
* @brief 将整数转化为字符串.
* @return 字符串
*/
string toString() {
stringstream result;
bool started = false; // 用于跳过前导0
for (auto i = elems.rbegin(); i != elems.rend(); i++) {
if (started) { // 如果多余的0已经都跳过,则输出
result << setw(RADIX_LEN) << setfill('0') << *i;
} else {
result << *i;
started = true; // 碰到第一个非0的值,就说明多余的0已经都跳过
}
}

if (!started) return "0"; // 当x全为0时
else return result.str();
}

/**
* @brief 大整数乘法.
* @param[in] x x
* @param[in] y y
* @return 大整数
*/
static BigInt multiply(const BigInt &x, const BigInt &y) {
vector z(x.elems.size() + y.elems.size(), 0);

for (size_t i = 0; i < y.elems.size(); i++) {
for (size_t j = 0; j < x.elems.size(); j++) { // 用y[i]去乘以x的各位
// 两数第i, j位相乘,累加到结果的第i+j位
z[i + j] += y.elems[i] * x.elems[j];

if (z[i + j] >= BIGINT_RADIX) { // 看是否要进位
z[i + j + 1] += z[i + j] / BIGINT_RADIX; // 进位
z[i + j] %= BIGINT_RADIX;
}
}
}
while (z.back() == 0) z.pop_back(); // 没有进位,去掉最高位的0
return BigInt(z);
}

private:
typedef long long int64_t;
/** 一个数组元素对应9个十进制位,即数组是亿进制的
* 因为 1000000000 * 1000000000 没有超过 2^63-1
*/
const static int BIGINT_RADIX = 1000000000;
const static int RADIX_LEN = 9;
/** 万进制整数. */
vector elems;
BigInt(const vector num) : elems(num) {}
};


class Solution {
public:
string multiply(string num1, string num2) {
BigInt x(num1);
BigInt y(num2);
return BigInt::multiply(x, y).toString();
}
};
```
{% endif %}