首页 > 代码库 > Leetcode | Multiply Strings

Leetcode | Multiply Strings

2024-07-03 23:53:13   216人阅读

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.

还是不要想得太复杂。一开始还想着要4位4位二分去做。其实只要一位一位地乘，小心地维护好进位就好。

 1 class Solution {
 2 public:
 3     string multiply(string num1, string num2) {

 4         if (num1.empty()) return "";
 5         if (num2.empty()) return "";
 6         int m1, m2, carry, val;
 7         
 8         reverse(num1.begin(), num1.end());
 9         reverse(num2.begin(), num2.end());
10         string ret(num1.length() + num2.length(), ‘0‘);
11         for (int i = 0; i < num2.length(); ++i) {
12             m2 = num2[i] - ‘0‘;
13             carry = 0;
14             for (int j = 0; j < num1.length(); ++j) {
15                 m1 = num1[j] - ‘0‘;
16                 val = m2 * m1 + carry + ret[i + j] - ‘0‘;
17                 ret[i + j] = val % 10 + ‘0‘;
18                 carry = val / 10;
19             }
20             ret[i + num1.length()] += carry;
21         }
22 
23         string r = "0";
24         for (int i = ret.length() - 1; i >= 0; --i) {
25             if (ret[i] != ‘0‘) {
26                 r = ret.substr(0, i + 1);
27                 break;
28             }
29         }
30         reverse(r.begin(), r.end());
31         return r;
32     }
33 };

reverse主要是便于取下标。

第10行，注意结果最大长度就是两个串的长度和；

第16行，注意每个位置需要加上ret[i+j]-‘0‘; 第17行，直接等于新的余数；

第20行，记得要把最后的进位保存下来；

第23行，如果从后往前扫一直没找到非零的数，那么证明结果为0，所以默认值设为‘0‘；


联系
我们