0415. 字符串相加 #
- 标签:数学、字符串、模拟
- 难度:简单
题目大意 #
描述:给定两个字符串形式的非负整数 num1
和num2
。
要求:计算它们的和,并同样以字符串形式返回。
说明:
- $1 \le num1.length, num2.length \le 10^4$。
- $num1$ 和 $num2$ 都只包含数字 $0 \sim 9$。
- $num1$ 和 $num2$ 都不包含任何前导零。
- 你不能使用任何內建 BigInteger 库, 也不能直接将输入的字符串转换为整数形式。
示例:
- 示例 1:
|
|
- 示例 2:
|
|
解题思路 #
思路 1:双指针 #
需要用字符串的形式来模拟大数加法。
加法的计算方式是:从个位数开始,由低位到高位,按位相加,如果相加之后超过 10
,就需要向前进位。
模拟加法的做法是:
- 用一个数组存储按位相加后的结果,每一位对应一位数。
- 然后分别使用一个指针变量,对两个数
num1
、num2
字符串进行反向遍历,将相加后的各个位置上的结果保存在数组中,这样计算完成之后就得到了一个按位反向的结果。 - 最后返回结果的时候将数组反向转为字符串即可。
注意需要考虑 num1
、num2
不等长的情况,让短的那个字符串对应位置按 $0$ 计算即可。
思路 1:代码 #
|
|
思路 1:复杂度分析 #
- 时间复杂度:$O(max(m + n))$。其中 $m$ 是字符串 $num1$ 的长度,$n$ 是字符串 $num2$ 的长度。
- 空间复杂度:$O(max(m + n))$。