字符串相乘(字符串,leetcode43)-------------------c++实现
字符串相乘(字符串,leetcode43)-------------------c++实现
题目表述
给定两个以字符串形式表示的非负整数 num1 和 num2,返回 num1 和 num2 的乘积,它们的乘积也表示为字符串形式。
注意:不能使用任何内置的 BigInteger 库或直接将输入转换为整数。
样例
输入: num1 = “2”, num2 = “3”
输出: “6”
条件
1 <= num1.length, num2.length <= 200
num1 和 num2 只能由数字组成。
num1 和 num2 都不包含任何前导零,除了数字0本身。
思路
利用加法做乘法(leetcode415是加法)
ac代码
c++:
class Solution {
public:
string addstring(string a,string b){
int i=a.size()-1,j=b.size()-1;
string result;
int nextmember=0;
while(i>=0||j>=0||nextmember!=0){
int x=(i>=0?a[i]-'0':0);
int y=(j>=0?b[j]-'0':0);
result.push_back((x+y+nextmember)%10+'0');
if((x+y+nextmember)>=10)
nextmember=1;
else
nextmember=0;
i--,j--;
}
reverse(result.begin(),result.end());
return result;
}
string multiply(string num1, string num2) {
if(num1.size()==1&&num1[0]=='0'||num2.size()==1&&num2[0]=='0')
return "0";
string result="0";
for( int i=num1.size()-1;i>=0;i--)
{
string now;
int next=0;
int bedo=num1[i]-'0';
for(int z=i;z<num1.size()-1;z++)
now+='0';
int j=num2.size()-1;
while(j>=0||next!=0)
{
int x=j>=0?num2[j]-'0':0;
now.push_back((x*bedo+next)%10+'0');
next=(x*bedo+next)/10;
j--;
}
reverse(now.begin(),now.end());
result=addstring(result,now);
}
return result;
}
};
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/squares-of-a-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。