欢迎光临散文网 会员登陆 & 注册

415. 字符串相加

2023-07-18 01:28 作者:目标力扣Knight  | 我要投稿

415. 字符串相加

方法一:高精度加法

将字符串转化为数字构成的数组,先分别逆序。然后将其按照较长数组对齐,从最低位开始累加,将每次两个数组之和与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函数;

  • C++字符串流会直接将整个字符串插入数组,而非拆分原字符串中每个字符单独插入;


415. 字符串相加的评论 (共 条)

分享到微博请遵守国家法律