Problem
Given two non-negative integers num1
and num2
represented as strings, return the product of num1
and num2
, also represented as a string.
Example 1:
Input: num1 = "2", num2 = "3" Output: "6"
Example 2:
Input: num1 = "123", num2 = "456" Output: "56088"
Note:
- The length of both
num1
andnum2
is < 110. - Both
num1
andnum2
contain only digits0-9
. - Both
num1
andnum2
do not contain any leading zero, except the number 0 itself. - You must not use any built-in BigInteger library or convert the inputs to integer directly.
Solution: Simulation
Simulate multiplication one digit at a time.
Time complexity: O(l1*l2)
Space complexity: O(l1 + l2)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
// Author: Huahua // Running time: 4 ms class Solution { public: string multiply(string num1, string num2) { const int l1 = num1.length(); const int l2 = num2.length(); string ans(l1 + l2, '0'); for (int i = l1 - 1; i >= 0; --i) for (int j = l2 - 1; j >= 0; --j) { int sum = (ans[i + j + 1] - '0') + (num1[i] - '0') * (num2[j] - '0'); ans[i + j + 1] = (sum % 10) + '0'; ans[i + j] += sum / 10; } for (int i = 0; i < ans.length(); ++i) if (ans[i] != '0' || i == ans.length() - 1) return ans.substr(i); return ""; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment