LeetCode刷题-43.字符串相乘
题目链接:43.字符串相乘
¶题解:
高精度乘以高精度!
¶题目简述:
两个字符串高精度相乘返回结果的字符串!
¶题解:
模拟小学乘法即可!
两个数相乘,最后积的位数为两数长度之和或者为长度之和减 1 !
思路:
- 先将字符串映射成数字,再倒序存到数组,为了方便计算!
- 两层循环,让第二个数的每一位去乘第一个数,存到新数组
c[i + j]
,这样可以保证该放到同一列的都在同一列 - 然后将需要进位的给了下一位,即
c[i + j + 1] += c[i + j] / 10
- 再将本位的余数留下即可,即
c[i + j] %= 10
- 最后需要将末尾的零去掉,即反转为正常数字的前导0.(例如乘以0,或者位数为两数之和减 1)
- 在将其映射为字符串,倒序存储到新数组,返回!
算了,懒得画图了,太好理解了!
时间复杂度: O(n * m)
¶AC代码:
1 |
|
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 小牛博客!
评论