当前位置:网站首页>【43. 字符串相乘】
【43. 字符串相乘】
2022-08-11 07:13:00 【安河桥畔】
字符串相加
题目来源
力扣(LeetCode): 字符串相乘
题目描述
给定两个以字符串形式表示的非负整数 num1 和 num2,返回 num1 和 num2 的乘积,它们的乘积也表示为字符串形式。
注意:不能使用任何内置的 BigInteger 库或直接将输入转换为整数。
示例1
输入
num1 = “2”, num2 = “3”
输出
“6”
示例2
输入
num1 = “123”, num2 = “456”
输出
“56088”
提示
- 1 <= num1.length, num2.length <= 200
- num1 和 num2 只能由数字组成。
- num1 和 num2 都不包含任何前导零,除了数字0本身。
思路分析
- 排除有’0’的情况
- 定义一个字符串保存乘积结果,这个串的长度是两个乘数长度之和
- 两层循环,从低位到高位开始相乘,这里必须将两个数全部转换为int类型相乘,定义临时变量保存乘积
- ▲用k表示当前乘积要保存在的位置,如果有进位则将进位结果保存在k-1的位置,由于char类型范围较小,所以乘积不能直接与ret当前位置的值相加,否则有可能超出char类型取值范围,如:得到乘积81若与’0’相加超出char类型范围。正确的处理方式:先将乘积结果进位保留个位与ret当前位相加,并再次处理加和的进位
- 结果放入字符串中时要转换成char类型,因为字符串每个位置都被初始化为了’0’,所以只需要将乘积加到对应位置即可
- 得到结果后,去除最高位的’0’
代码展示
class Solution {
public:
string multiply(string num1, string num2) {
//有一个乘数为0则积为0
if (num1 == "0" || num2 == "0")
{
return "0";
}
//找较长的串作左操作数(个人习惯,这步可以省略)
if (num1.size() < num2.size())
{
num1.swap(num2);
}
int LeftSize = num1.size();
int RightSize = num2.size();
//保存乘积的字符串,两个数乘积最大位数为两个数位数之和
int RetSize = LeftSize + RightSize;
string ret(RetSize, '0');
int m = 1;//m标记保存结果数据的起始位
for (int i = RightSize - 1; i >= 0; i--)
{
int k = RetSize - m;
for (int j = LeftSize - 1; j >= 0; j--)
{
//定义临时变量保存乘积,int类型
int temp = (num2[i] - '0') * (num1[j] - '0');
//进位,因为乘积最大位81,加上'0'会超出char类型范围,所以要分两次处理进位
ret[k - 1] += temp / 10;
temp %= 10;
ret[k] += temp;
//临时变量temp加到ret字符串中后还要再次处理进位
while (ret[k] > '9')
{
ret[k] -= 10;
ret[k - 1] += 1;
}
k--;//ret中保存结果的位置左移
}
m++;//ret中保存结果的起始位置左移一位
}
//去除最高位的'0'
int count = 0;
for (auto ch : ret)
{
if (ch != '0')
{
break;
}
count++;
}
ret.erase(0, count);
return ret;
}
};
总结
难点及易错点:
- 忽略有’0’的情况
- 两次处理进位结果
- 对于int类型,可以用“除10”和“模10”处理进位
- 保存结果的字符串位置的偏移,内层循环每次结束左移一位,外层循环每轮结束将起始位置左移一位
- 去除结果最高位的’0’
边栏推荐
- redis操作
- redis operation
- [Recommender System]: Overview of Collaborative Filtering and Content-Based Filtering
- TF中的条件语句;where()
- Write a resume like this, easy to get the interviewer
- Conditional statements in TF; where()
- 1061 判断题 (15 分)
- 为什么C#中对MySQL不支持中文查询
- Redis source code: how to view the Redis source code, the order of viewing the Redis source code, the sequence of the source code from the external data structure of Redis to the internal data structu
- 为什么我使用C#操作MySQL进行中文查询失败
猜你喜欢
1071 Small Gamble (15 points)
TF中使用softmax函数;
4.1-支持向量机
囍楽云任务源码
Decrement operation in tf; tf.assign_sub()
Redis source code-String: Redis String command, Redis String storage principle, three encoding types of Redis string, Redis String SDS source code analysis, Redis String application scenarios
Pico neo3在Unity中的交互操作
One-hot in TF
【LeetCode】Summary of linked list problems
1101 How many times B is A (15 points)
随机推荐
流式结构化数据计算语言的进化与新选择
break pad源码编译--参考大佬博客的总结
1091 N-Defensive Number (15 points)
1106 2019数列 (15 分)
1081 Check Password (15 points)
1046 punches (15 points)
Square, multi-power, square root calculation in Tf
oracle19c不支持实时同步参数,请教一下大佬们有什么好的解决办法吗?
Conditional statements in TF; where()
linux 安装mysql服务报错
Redis source code-String: Redis String command, Redis String storage principle, three encoding types of Redis string, Redis String SDS source code analysis, Redis String application scenarios
Tf中的平方,多次方,开方计算
Implementation of FIR filter based on FPGA (5) - FPGA code implementation of parallel structure FIR filter
Two startup methods and differences of Service
欢迎加入sumarua网络安全交流社区
分布式锁-Redission - 缓存一致性解决
【latex异常和错误】Missing $ inserted.<inserted text>You can‘t use \spacefactor in math mode.输出文本要注意特殊字符的转义
oracle19c does not support real-time synchronization parameters, do you guys have any good solutions?
2.1 - Gradient Descent
2021-08-11 For loop combined with multi-threaded asynchronous query and collect results