415. 字符串相加
2023-07-18 01:28 作者:目标力扣Knight | 我要投稿

方法一:高精度加法
将字符串转化为数字构成的数组,先分别逆序。然后将其按照较长数组对齐,从最低位开始累加,将每次两个数组之和与10取模数后的余数存入数组,再输出,最后将其转换为字符串即可,Python可以使用map函数,C++只能遍历硬转。
Python版本
C++版本
复杂度分析
时间复杂度:O(N)。令两数组中较长数组长度为n,那么转换为数字构成的数组,消耗2N,逆序遍历2N,计算复杂度为N,输出后转化为字符串为N,则最终复杂度约为6N;
空间复杂度:O(N)。分别需要两个数组存储转换为数字的数组,则依照上文,空间约为2N,函数栈存储求和后的数组消耗约为N或者N+1, 最后转换数据类型消耗N,最终复杂度约为 4N;
备注
Python中字符串的
join
函数需要手动遍历,否则请使用map函数;