中材矿山建设有限公司网站,免费企业网站源代码,网站建设与运营及营销服务,360云主机可以建设网站吗文章目录1. 题目2. 小学竖式乘法2.1 普通版2.2 优化版1. 题目
给定两个以字符串形式表示的非负整数 num1 和 num2#xff0c;返回 num1 和 num2 的乘积#xff0c;它们的乘积也表示为字符串形式。
示例 1:
输入: num1 2, num2 3
输出: 6返回 num1 和 num2 的乘积它们的乘积也表示为字符串形式。
示例 1:
输入: num1 2, num2 3
输出: 6示例 2:
输入: num1 123, num2 456
输出: 56088说明
num1 和 num2 的长度小于110。
num1 和 num2 只包含数字 0-9。
num1 和 num2 均不以零开头除非是数字 0 本身。
不能使用任何标准库的大数类型比如 BigInteger或转换为整数来处理。来源力扣LeetCode 链接https://leetcode-cn.com/problems/multiply-strings 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
类似题目LeetCode 415. 字符串相加大数加法
2. 小学竖式乘法
2.1 普通版 class Solution {
public:string multiply(string num1, string num2) {if(num1 0 || num2 0)return 0;int n1 num1.size(), n2 num2.size(), i, j;int bit1, bit2, carry, zero, curBit;string ans, temp;for(i n2-1; i 0; i--){carry 0;//进位清零temp ;//临时乘积zero n2-1-i;//后置添0个数while(zero--)temp.push_back(0);bit2 num2[i]-0;for(j n1-1; j 0 || carry ! 0; --j){bit1 j 0 ? 0 : (num1[j]-0);curBit (bit1*bit2carry)%10;temp.push_back(curBit0);carry (bit1*bit2carry)/10;}reverse(temp.begin(),temp.end());//上面临时乘积是逆序的ans addStrings(ans,temp);//调用大数加法}return ans;}//LeetCode 415. 字符串相加大数加法string addStrings(string num1, string num2) {int n1 num1.length(), n2 num2.length();int i n1-1, j n2-1, one 0, bit1, bit2, curBit;string ans;for( ; i 0 || j 0; --i,--j){bit1 i0 ? 0 : (num1[i]-0);bit2 j0 ? 0 : (num2[j]-0);curBit (bit1bit2one)%10;one (bit1bit2one)/10;ans.push_back(curBit0);}if(one)ans.push_back(1);reverse(ans.begin(),ans.end());return ans;}
};2.2 优化版 class Solution {
public:string multiply(string num1, string num2) {if(num1 0 || num2 0)return 0;int n1 num1.size(), n2 num2.size(), i, j, curSum;int bit1, bit2, len n1n2;int res[len] {0};//两数的乘积最多是n1n2位string ans, temp;for(i n2-1; i 0; i--){bit2 num2[i]-0;for(j n1-1; j 0; --j){bit1 num1[j]-0;curSum res[ij1] bit1*bit2;res[ij1] curSum % 10;res[ij] curSum / 10;}}for(i 0; i len; i){if(i 0 res[i] 0)continue;//前面可能有一个0跳过ans.append(to_string(res[i]));}return ans;}
};
