学生网站建设实训总结,phpcms 后台修改修改网站备案号,织梦怎么关闭网站,宿州保洁公司有哪些目录链接#xff1a;
力扣编程题-解法汇总_分享记录-CSDN博客 GitHub同步刷题项目#xff1a;
https://github.com/September26/java-algorithms 原题链接#xff1a;力扣#xff08;LeetCode#xff09;官网 - 全球极客挚爱的技术成长平台 描述#xff1a;
给定两个以…目录链接
力扣编程题-解法汇总_分享记录-CSDN博客 GitHub同步刷题项目
https://github.com/September26/java-algorithms 原题链接力扣LeetCode官网 - 全球极客挚爱的技术成长平台 描述
给定两个以字符串形式表示的非负整数 num1 和 num2返回 num1 和 num2 的乘积它们的乘积也表示为字符串形式。
注意不能使用任何内置的 BigInteger 库或直接将输入转换为整数。 示例 1:
输入: num1 2, num2 3
输出: 6
示例 2:
输入: num1 123, num2 456
输出: 56088 提示
1 num1.length, num2.length 200num1 和 num2 只能由数字组成。num1 和 num2 都不包含任何前导零除了数字0本身。
解题思路
* 解题思路
* 我们就按照乘法的定义来把num1和num2转换成两个int类型的数组v1和v2。
* 然后用v2的每一位乘以v1数组得到一个新的数组。比如v1是[1,2,3]v2的位置上的数字位2得到的结果就是[2,4,6]。
* 然后我们可以得到多个这样的数组求这些数组的和即可。注意的时后面的数组前面要插入若干个0.
* 比如200和[1,2,3]前面就需要插入两个0. 代码
class Solution43
{
public:vectorint multiplyItem(vectorint v1, int value){vectorint result;int carryValue 0;for (int i : v1){int newValue value * i carryValue;carryValue newValue / 10;result.push_back(newValue % 10);}if (carryValue 0){result.push_back(carryValue);}return result;}/*** 两个list合并*/vectorint merge(vectorint oldList, int startIndex, vectorint newList){for (int i 0; i startIndex; i){newList.insert(newList.begin(), 0);}int index 0;int carry 0;vectorint list;while (index oldList.size() || index newList.size() || carry 0){int oldValue 0;int newValue 0;if (index oldList.size()){oldValue oldList[index];}if (index newList.size()){newValue newList[index];}int value oldValue newValue carry;carry value / 10;list.push_back(value % 10);index;}return list;}string multiply(string num1, string num2){vectorint v1;vectorint v2;for (char c : num1){v1.insert(v1.begin(), c - 0);}for (char c : num2){v2.insert(v2.begin(), c - 0);}vectorint result;int index 0;int leftStart 0;for (int i 0; i v2.size(); i){vectorint newList multiplyItem(v1, v2[i]);result merge(result, i, newList);}string s;bool isStart false;for (int i 0; i result.size(); i){s.insert(0, to_string(result[i]));}string ss;for (char c : s){if (ss.size() 0 c 0){continue;}ss.push_back(c);}return ss.size() 0 ? 0 : ss;}
};
