415. 字符串相加
查看题目简单
字符串
高频
解法一:迭代法
时间复杂度:O(max(m, n)) | 空间复杂度:O(max(m, n)) | 推荐使用
动画演示
准备就绪 - 输入两个字符串数字,然后点击开始
代码实现
class Solution {
/**
* 字符串相加算法
* 使用迭代方法实现两个字符串表示的非负整数相加
*/
public String addStrings(String num1, String num2) {
int i = num1.length() - 1, j = num2.length() - 1, add = 0;
StringBuffer ans = new StringBuffer();
while (i >= 0 || j >= 0 || add != 0) {
int x = i >= 0 ? num1.charAt(i) - '0' : 0;
int y = j >= 0 ? num2.charAt(j) - '0' : 0;
int result = x + y + add;
ans.append(result % 10);
add = result / 10;
i--;
j--;
}
// 计算完以后的答案需要翻转过来
ans.reverse();
return ans.toString();
}
}时间复杂度:O(max(m, n))
空间复杂度:O(max(m, n))
算法思路:
使用迭代方法实现两个字符串表示的非负整数相加,模拟手动加法的过程。
核心思想:
1. 从两个字符串的末尾开始遍历,逐位相加
2. 维护一个进位变量,处理相加结果大于等于10的情况
3. 将每一位的计算结果添加到结果字符串中
4. 遍历结束后,如果还有进位,将其添加到结果字符串
5. 最终将结果字符串反转,得到正确的相加结果
复杂度分析:
- 时间复杂度:O(max(m, n)),其中m和n分别是两个输入字符串的长度,只需遍历一次
- 空间复杂度:O(max(m, n)),最坏情况下结果字符串的长度为max(m, n) + 1