【LeetCode】43. Multiply Strings

2019-11-06 07:34:21

字体：大中小

来源：转载

供稿：网友

题目描述

Given two non-negative integers num1 and num2 rePResented as strings, return the product of num1 and num2.

Note:

The length of both num1 and num2 is < 110.Both num1 and num2 contains only digits 0-9.Both num1 and num2 does not contain any leading zero.You must not use any built-in BigInteger library or convert the inputs to integer directly.

解题思路

大数相乘。为了解题思路清晰，我是自己模拟手工相乘的方法做的。具体见代码注释。

AC代码

class Solution {public: //给数组左边加0，使其最终长度为tLen string leftPad(string num, int tLen) { int numLen = num.size(); string zero(tLen - numLen, '0'); return zero + num; } //大数相加。先将两个大数前面补0使其长度相同，注意最后的carry string strAdd(string num1, string num2) { int maxLen = max(num1.size(), num2.size()); num1 = leftPad(num1, maxLen); num2 = leftPad(num2, maxLen); string ans; int carry = 0; for (int idx = maxLen - 1; idx >= 0; --idx) { int curSum = (num1[idx] - '0') + (num2[idx] - '0'); curSum += carry; ans.push_back((curSum % 10) + '0'); carry = curSum / 10; } if (carry != 0) ans.push_back(carry + '0'); reverse(ans.begin(), ans.end()); return ans; } //大数相乘。每次使用一个位与另一个数字相乘，然后通过大数相加更新答案。 string multiply(string num1, string num2) { if (num2 == "0" || num1 == "0") return "0"; string ans; for (int i = num2.size() - 1; i >= 0; --i) { if (num2[i] == '0') continue; string curAns; int carry = 0; for (int j = num1.size() - 1; j >= 0; --j) { int mul = (num2[i] - '0') * (num1[j] - '0'); mul += carry; curAns.push_back((mul % 10) + '0'); carry = mul / 10; } if (carry != 0) curAns.push_back(carry + '0'); reverse(curAns.begin(), curAns.end()); string zeros(num2.size() - i - 1, '0'); ans = strAdd(ans, curAns + zeros); } return ans; }};

上一篇：Spring_AOP

下一篇：golang中读写锁RWMutex和通用锁Mutex的使用

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注