Leetcode_43. 字符串相乘
✨✨ 欢迎大家来到小伞的大讲堂✨✨
🎈🎈养成好习惯，先赞后看哦~🎈🎈
所属专栏：C++_OJ
小伞的主页：xiaosan_blog
字符串相乘
43. 字符串相乘 - 力扣（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本身。
解题思路
暴力解法：
创建两个变量，分别保存字符串的整型值，在相乘，转回字符串
注：此解法并不能通过，因为unsigned类型范围为2^32，由于力扣会输入大量数据，导致超过量程，报错(针对于小数据)
模拟乘法：
注：我们单取每一位的数相乘，并非暴力解法中，将所有数取出，创建add为进位数，每次取下一位时，与add相加
为了更好地理解，代码如下
class Solution {
public:
string addStrings(string& num1, string& num2) {
//模拟实现乘法，加法过程
int i = num1.size() - 1, j = num2.size() - 1, add = 0;
string ans;
while (i >= 0 || j >= 0 || add != 0) {
int x =i >= 0 ? num1.at(i) - '0' : 0;//预防访问字符下标小于0
int y =j >= 0 ? num2.at(j) - '0' : 0;
int result = x + y + add;
ans.push_back(result % 10+'0');
add = result / 10;
i--;
j--;
}
reverse(ans.begin(), ans.end());//每次反转
return ans;
}
string multiply(string num1, string num2) {
if (num1 == "0" || num2 == "0") {
return "0";
}
int sum1 = 0; // 取值
int sum2 = 0;
string ans = "0";
int len1 = num1.size(); // 长度
int len2 = num2.size();
int x = 0; // 总和
int y = 0; // 插入
int i = 0;
auto it2 = num2.rbegin();
//反向迭代器，因为字符串每次取数为高位
//我们需要从个位往高位取，所以使用反向迭代器
while (it2 != num2.rend()) {
string s;
int add = 0; // 进位数
auto it1 = num1.rbegin();//个位数与其他位数的乘法模拟
while (it1 != num1.rend()) {// 单个num2的数与num1乘积储存
// 依次取值
sum1 = *it1 - '0';
sum2 = *it2 - '0';
x = sum1 * sum2 + add;
add = x / 10;//进位数
y = x % 10;//取余
s.push_back(y + '0');
it1++;
}
if (add != 0) {//说明单次乘法结束，还有进位数的存在
s.push_back(add + '0');
}
reverse(s.begin(), s.end());//反转，因为插入顺序与目标顺序相反
it2++;
// 判断差几位，每次乘，需要乘10，添0；
//如果是十位数相乘，我们相乘的结果都认为是个位数相乘，还原回去，此时乘出的值需要加'0'
for (int j = i; j > 0; j--) {
s.push_back('0');
}
i++;
ans = addStrings(ans, s);//ans第一次进入为‘0’// 与前面相加//竖式的实现
}
return ans;
}
};