当前位置 博文首页 > yumoz:LeetCode43--字符串相乘
给定两个以字符串形式表示的非负整数 num1 和 num2,返回 num1 和 num2 的乘积,它们的乘积也表示为字符串形式。
//1.判断单独有“0” 和 "1"的情况
if(num1=="0" || num2=="0") return "0";
if(num1=="1") return num2;
if(num2=="1") return num1;
//2. 保证效率,让大数乘小数
if(num1.length() < num2.length())
swap(num1,num2);
// 3. 测长度,开字符串
int m = num1.length(), n = num2.length();
//提前开一个足够大的string,m位数和n位数的乘法结果不会超过m+n位数
string res(m+n,'0');
new_num = (num1[j]-'0')*(num2[i]-'0') + (res[i+j+1]-'0') + c_in;
总结:此段代码,有效的结合进位,叠加等方式,依次推出每个位的值,最后通过计算得出最终答案。
//4. 计算相乘
for(int i = n-1; i>=0; --i){
int c_in = 0; //进位
for(int j = m-1; j>=0; --j){
//乘法加法进位一口气算完
int new_num = (num1[j]-'0')*(num2[i]-'0') + (res[i+j+1]-'0') + c_in;
c_in = new_num / 10; //进位
new_num = new_num % 10; //求出
res[i+j+1] = char(new_num + '0'); //转成字符类型
}
if(c_in > 0) res[i] = char(c_in + '0');//有进位,加进位
}
int i = 0;
while(res[i] == '0') i++;
return res.substr(i,m+n-i); //去掉前面多余的0
class Solution {
public:
string multiply(string num1, string num2) {
//1.判断单独有“0” 和 "1"的情况
if(num1=="0" || num2=="0") return "0";
if(num1=="1") return num2;
if(num2=="1") return num1;
//2. 保证效率,让大数乘小数
if(num1.length() < num2.length())
swap(num1,num2);
// 3. 测长度,开字符串
int m = num1.length(), n = num2.length();
//提前开一个足够大的string,m位数和n位数的乘法结果不会超过m+n位数
string res(m+n,'0');
//4. 计算相乘
for(int i = n-1; i>=0; --i){
int c_in = 0; //进位
for(int j = m-1; j>=0; --j){
//乘法加法进位一口气算完
int new_num = (num1[j]-'0')*(num2[i]-'0') + (res[i+j+1]-'0') + c_in;
c_in = new_num / 10; //进位
new_num = new_num % 10; //求出
res[i+j+1] = char(new_num + '0'); //转成字符类型
}
if(c_in > 0) res[i] = char(c_in + '0');//有进位,加进位
}
int i = 0;
while(res[i] == '0') i++;
return res.substr(i,m+n-i); //去掉前面多余的0
}
};
此篇博客代码参考于大牛写的一个题解,作为一种新的处理方法。
cs