8000 added 124. Multiply Strings · hustfc/LeetCode@43818fd · GitHub
[go: up one dir, main page]
Skip to content

Commit 43818fd

Browse files
pezypezy
committed
added 124. Multiply Strings
1 parent d1fedd0 commit 43818fd

File tree

3 files changed

+77
-0
lines changed

3 files changed

+77
-0
lines changed

‎124. Multiply Strings/README.md

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
这道题就是考察大数乘法了。
2+
3+
我们还是从简单的例子来分析：
4+
5+
1234567 *
6+
8901234
7+
8+
想想，乘法是如何运算的，用比较小的数举例，更好理解：
9+
10+
23 *
11+
43
12+
----
13+
69 +
14+
92
15+
-----
16+
989
17+
18+
我们将 43 视作 num1, 23 视作 num2, 那么这是一个很明显的两级 `for` 循环。从尾部开始，外部遍历 num1, 内部遍历 num2. 注意进位。
19+
20+
如果给定的是字符串，显然，我们是从字符串的末尾开始遍历的。
21+
22+
另外一个隐藏的规律是：num1 * num2 结果的位数必然小于 num1 的位数 + num2 的位数。
23+
所以可以设结果为 `string ret(num1.size() + num2.size(), '0');`
24+
25+
```cpp
26+
for (size_t i = num1.size()-1; i >= 0; --i) {
27+
int carry = 0;
28+
for (size_t j = num2.size()-1; j >= 0; --j) {
29+
int sum = (ret[i+j+1] - '0') + (num1[i] - '0') * (num2[j] - '0') + carry;
30+
ret[i+j+1] = sum % 10 + '0';
31+
carry = sum / 10;
32+
}
33+
ret[i] += carry;
34+
}
35+
```
36+
37+
得到的结果依旧是从尾部开始铺陈开的，所以最终还要去掉开头初始化时的 `0`。
38+
39+
```cpp
40+
size_t pos = ret.find_first_not_of('0');
41+
if (pos != string::npos) return ret.substr(pos);
42+
else return "0";
43+
```
44+
45+
提交 AC.

‎124. Multiply Strings/TEST.cc

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
1+
#define CATCH_CONFIG_MAIN
2+
#include "../Catch/single_include/catch.hpp"
3+
#include "solution.h"
4+
5+
TEST_CASE("Multiply Strings", "multiply")
6+
{
7+
Solution s;
8+
9+
REQUIRE(s.multiply("123456", "789") == "97406784");
10+
REQUIRE(s.multiply("123456789", "987654321") == "121932631112635269");
11+
}

‎124. Multiply Strings/solution.h

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
#include <string>
2+
using std::string;
3+
4+
class Solution {
5+
public:
6+
string multiply(string num1, string num2) {
7+
string ret(num1.size() + num2.size(), '0');
8+
for (int i = num1.size()-1; i >= 0; --i) {
9+
int carry = 0;
10+
for (int j = num2.size()-1; j >= 0; --j) {
11+
int sum = (ret[i+j+1]-'0') + (num1[i]-'0') * (num2[j]-'0') + carry;
12+
ret[i+j+1] = sum%10 + '0';
13+
carry = sum/10;
14+
}
15+
ret[i] += carry;
16+
}
17+
size_t pos = ret.find_first_not_of('0');
18+
if (pos != string::npos) return ret.substr(pos);
19+
else return "0";
20+
}
21+
};

0 commit comments

Comments
 (0)
0