[C++]-字符串相加/字符串相乘
目录
1.字符串相加
给定两个字符串形式的非负整数 num1 和num2 ,计算它们的和并同样以字符串形式返回。你不能使用任何內建的用于处理大整数的库(比如 BigInteger), 也不能直接将输入的字符串转换为整数形式。
示例 1: 输入:num1 = "11", num2 = "123"
输出:"134"
示例 2: 输入:num1 = "456", num2 = "77"
输出:"533"
示例 3: 输入:num1 = "0", num2 = "0"
输出:"0"
首先我们需要了解字符和数字之间的转换,需要了解ASCII码。其中字符'0'对应十进制48,字符'9'对应十进制57。将字符'x'转换为整型,可以使用'x' - 48 或者 'x' - '0' 。
首先需要将字符串尾部对齐相加(转换为int),保留进位,当较短字符串前几位时使用0代替。将所加的值尾插到新字符串中,最后将新字符串翻转即可得到结果。(若是一直头插,会一直挪动,导致效率低下)。具体代码如下
class Solution {
public:
string addStrings(string num1, string num2)
{
//计算num1,num2大小
int end1 = num1.size() - 1;
int end2 = num2.size() - 1;
//新字符串
std::string retstr;
//进位
int carry = 0;
//预先开空间
retstr.reserve(end1 > end2 ? end1 : end2);
//两个字符串走完跳出循环
while( end1 >= 0 || end2 >= 0)
{
//若是有一个字符串走完则使用0代替该位置
int val1 = end1 >= 0 ? num1[end1] - '0' : 0;
int val2 = end2 >= 0 ? num2[end2] - '0' : 0;
int ret = val1 + val2 + carry;
carry = ret / 10;
ret = ret % 10;
//retstr.insert(0,1,'0' + ret)
//尾插,保留字符串也可以(48 + ret)
retstr += ('0' + ret);
--end1;
--end2;
}
//若最后有一个进位1
if(carry != 0 )
retstr += '1';
reverse( retstr.begin(), retstr.end());
return retstr;
}
};
2.字符串相乘
给定两个以字符串形式表示的非负整数 num1 和 num2,返回 num1 和 num2 的乘积,它们的乘积也表示为字符串形式。
注意:不能使用任何内置的 BigInteger 库或直接将输入转换为整数。
示例 1: 输入: num1 = "2", num2 = "3"
输出: "6"
示例 2: 输入:num1 = "123", num2 = "456"
输出: "56088"
此题不同于第一题,需要对字符串1的每一位和字符串2的每一位相乘然后根据对应关系进行相加,相加时也需要考虑进位。此处使用两个for循环来完成计算。首先需要创建一个新字符串长度为num1.size() + num2.size(),置为全零,来存储相乘之后的结果。
class Solution {
public:
string multiply(string num1, string num2)
{
//num1,num2大小
int m = num1.size(),n = num2.size();
//新字符串 全为'0'
string res(m + n, '0');
//若有一个字符串为'0',返回'0'
if(m == 0 || n == 0 ) return "0";
//从num1最后一位字符开始计算
for(int i = m - 1; i >= 0; --i)
{
//每次从num2最后一位字符直到第一位字符
for(int j = n - 1; j >= 0; --j)
{
//将字符转换为int 相乘
int tmp = (num1[i] - '0') * (num2[j] - '0');
//将相乘后的结果保存到新字符串的对应位置。-'0' 是为了保证tmp为int
//+=保证进位加上来
tmp += res[i + j + 1] - '0';
//将tmp的个位数字+'0' 保存到字符串res对应位置
res[i + j + 1] = tmp % 10 + '0';
//第一个 -'0' 将字符串中字符换位数字
//第二个 +'0' 将计算后的结果保存为字符
res[i + j] = res[i + j] -'0' + tmp / 10 + '0';
}
}
//去掉前导零
//计算之后新字符串可能有部分零
int index = 0;
while(index < m+n-1 && res[index] =='0')
++index;
return res.substr(index);
}
};