🎈个人主页:🎈 :✨✨✨初阶牛✨✨✨
>🐻推荐专栏1: 🍔🍟🌯C语言初阶
🐻推荐专栏2: 🍔🍟🌯C语言进阶
🔑个人信条: 🌵知行合一
金句分享:
✨你要狠下心来去努力,努力变成一个很厉害的人.✨
前言
本题牛牛写了很久,起初对每次相乘的结果就进位处理了,最后还需要考虑错位相加,进行补0等,花了半天也没搞出来.
所幸学到了一种高效且相对简单的方法解决此题,希望对友友们有所帮助.
一、字符串相乘
题目介绍
给定两个以字符串形式表示的非负整数 num1 和 num2,返回 num1 和 num2 的乘积,它们的乘积也表示为字符串形式。
注意:不能使用任何内置的 BigInteger
库或直接将输入转换为整数。
示例1:
输入: num1 = “2”, num2 = “3”
输出: “6”
示例2:
输入: num1 = “123”, num2 = “456”
输出: “56088”
思路分析
-
同时从两个字符串的右边开始往前遍历相乘.
-
用
num2
中的每一个字符依次与与num1
中的每个字符想乘. -
将相乘的结果保存在一个
arr
数组中,每个相乘的结果放入正确的位置(i+J+1
). -
arr
数组创建多大的空间?
一个最小的二位数 × 一个最小的三位数 结果是一个四位数
10100=1000
一个最大的二位数 × 一个最大的三位数 结果是一个五位数
99999=98901
综上呢,两个数相乘,他们的结果的位数是[length1 + length2,length1 + length2+1]
,(0
除外哈)
最高位可能有数据,也可能没有数据. -
为什么正确的位置是
i+j+1
?
试着看上图分析:注意i
和j
都是从右边往左边遍历.
此处是此解法的难点,通过将每次相乘后的结果放入正确的位置以实现错位相加.
牛牛的理解是:j
是内循环,从右往左遍历num1
,i是外循环,决定的是num2
.
所以用j
的变化控制与num1
相乘结果的位置,用i
的变化,控制错位相加(即相乘的结果要往左移动一位)即num2
的位变化. -
对错位相加后的数组进行进位处理:从右往左进位
(1)先保存元素的值,tmp = arr[i]+carry;
(2)替换为进位后的数据:arr[i] = (arr[i] + carry) % 10;
(3)保存进位数:carry = tmp / 10;
-
将进位后的数组中的数据依次尾插入
amass
对象中.
注意:先判断第一个位置有没有有效数据(即最高位是否有效) -
最后,处理特殊情况,如果num1和num2中有一个是0,则直接返回0.文章来源:https://www.toymoban.com/news/detail-653758.html
代码实现:
class Solution {
public:
string multiply(string num1, string num2) {
//处理特殊情况,如果有一方为0,
if (num1[0] == '0' || num2[0] == '0') return string("0");
int length1 = num1.size();
int length2 = num2.size();
int arr[length1 + length2];
//将数组中的元素全部初始化为0
for (auto& a : arr)
{
a = 0;
}
string amass;
//相乘
//内外层循环控制num2和num1 的次序无所谓
//版本1
for (int i = length2 -1; i >= 0; i--){//外层循环控制num2
int s1 = num2[i] - '0';
for (int j = length1 - 1; j >= 0; j--){//内存循环控制num1
int s2 = num1[j] - '0';
arr[i+j+1] += s1 * s2;//注意这里是+=
}
}
//版本2
/*
for (int i = length1 - 1; i >= 0; i--)
{
int s1 = num1[i] - '0';
for (int j = length2 - 1; j >= 0; j--)
{
int s2 = num2[j] - '0';
arr[i + j + 1] += s1 * s2;//注意这里是+=
}
}
*/
//处理进位问题:
int carry = 0;
for (int i = length1 + length2 - 1; i >= 0; i--)
{
int tmp = arr[i]+carry; //保存当前位置中的元素大小,因为下一句代码会影响giabarr[j]
arr[i] = (arr[i] + carry) % 10; //存放个位数
carry = tmp / 10; //存放十位数(进位数
}
//第一个位置是否有元素,最高位是否有效
if (arr[0] != 0)
amass.push_back(arr[0] + '0');
//
for (int i = 1; i < length1 + length2; i++)
{
amass.push_back(arr[i] + '0');
}
return amass;
}
};
最后,感谢友友们阅读本篇解题分享,希望这篇文章对您在解决问题过程中有所帮助。在解题过程中,我们需要不断思考、尝试、调整,才能得出正确的解决方案。同时,我们也要记得不断学习、积累知识和经验,提升自己的能力。最后,祝您在解决问题的道路上越走越远,不断成长和进步。
文章来源地址https://www.toymoban.com/news/detail-653758.html
到了这里,关于如何高效解决“字符串相乘“问题?的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!