8000 added 124. Multiply Strings · lccate/LeetCode-1@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
  • solution.h

    • 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