415. 字符串相加
415. 字符串相加
题目
Given two non-negative integers, num1
and num2
represented as string, return the sum of num1
and num2
as a string.
You must solve the problem without using any built-in library for handling large integers (such as BigInteger
). You must also not convert the inputs to integers directly.
Example 1:
Input: num1 = "11", num2 = "123"
Output: "134"
Example 2:
Input: num1 = "456", num2 = "77"
Output: "533"
Example 3:
Input: num1 = "0", num2 = "0"
Output: "0"
Constraints:
1 <= num1.length, num2.length <= 10^4
num1
andnum2
consist of only digits.num1
andnum2
don't have any leading zeros except for the zero itself.
题目大意
给定两个字符串形式的非负整数 num1
和 num2
,计算它们的和并同样以字符串形式返回。
你不能使用任何內建的用于处理大整数的库(比如 BigInteger
), 也不能直接将输入的字符串转换为整数形式。
解题思路
反向遍历:从字符串的最后一位开始遍历,以便处理进位。这样可以从最低位开始相加,符合数学加法的规则。
逐位相加:逐位相加对应位置的数字。对于每一位,计算两个字符的数值,进行相加并考虑进位。
进位处理:如果某一位的和大于或等于
10
,则需要向下一位传递进位(carry
),并更新当前位的结果。处理剩余位和进位:遍历结束后,如果还有进位,则需要在结果字符串前添加进位。
结果构建:使用字符串拼接的方式构建最终结果,注意结果需要反向,因为我们是从低位到高位计算的。
复杂度分析
- 时间复杂度:
O(max(m, n))
,其中m
和n
是两个字符串的长度。需要遍历两个字符串的每一位。 - 空间复杂度:
O(max(m, n))
,用于存储结果字符串。
代码
/**
* @param {string} num1
* @param {string} num2
* @return {string}
*/
var addStrings = function (num1, num2) {
let result = '';
let carry = 0;
let i = num1.length - 1;
let j = num2.length - 1;
while (i >= 0 || j >= 0 || carry > 0) {
const x1 = i >= 0 ? num1[i] - '0' : 0; // num1 的当前位
const x2 = j >= 0 ? num2[j] - '0' : 0; // num2 的当前位
const sum = x1 + x2 + carry; // 当前位的和
result = (sum % 10) + result; // 结果的当前位,注意拼接方向
carry = Math.floor(sum / 10); // 更新进位
i--; // 移动到下一位
j--;
}
return result; // 返回最终结果
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 |
---|---|---|---|---|
2 | 两数相加 | [✓] | 递归 链表 数学 | |
43 | 字符串相乘 | [✓] | 数学 字符串 模拟 | |
989 | 数组形式的整数加法 | 数组 数学 |