Open
Description
[LeetCode] 415. Add Strings 字符串相加
给定两个字符串形式的非负整数 num1 和 num2，计算它们的和。
提示:
num1 和num2 的长度都小于 5100
num1 和num2 都只包含数字 0-9
num1 和num2 都不包含任何前导零
你不能使用任何內建 BigInteger 库， 也不能直接将输入的字符串转换为整数形式
方法一：模拟
思路与算法
本题我们只需要对两个大整数模拟 [竖式加法]的过程，竖式加法就是我们平时使用的对两个整数相加的方法，回想一下我们在纸上对两个整数相加的过程，是不是如下图将相同的数位对齐，从低位到高位逐位相加，如果当前位和超过10，则向高位进一位？因此我们只要将这个过程用代码写出来即可。
具体实现也不复杂，我们定义两个指针 i 和 j 分别指向 nums1 和 nums2的末尾，即最低位，同时定义一个变量 add 维护当前是否有进位，然后从末尾到开头逐位相加即可，你可能会想两个数字位数不相同应该如何处理，这里我们统一在指针当前下标处于负数的时候返回0，等价于对位数较短的数字进行了补零操作，这样就可以除去两个数字位数不同情况的处理，具体看下面代码。
var addStrings = function(num1, num2) {
let i = num1.length - 1; // 最后一个索引
let j = num2.length - 1;
let add = 0;
// 返回的是数组
const ans = [];
// 精髓就在这个while循环, 使用的是或
while(i >= 0 || j >= 0 || add != 0 ) {
// 这部分涉及一个js的语法技巧，js 是弱类型的语言，如果两个数字型的字符相减
// 或者其中一个为字符串时，那么会自动转换为 number类型进行运算
// '1000' - '200' = 800;
// 1000 - '800' = 200;
// 1000 > '800' true
// 所以下面这两句代码 �就是将当前的这个位置上的数字转换为 数字
const x = i >= 0 ? num1.charAt(i) - '0' : 0;
const y = j >= 0 ? num2.charAt(j) - '0' : 0;
// 结果
const result = x + y + add;
// 放进去的是对 10 取余的
ans.push(result % 10);
// 0-9 和 0-9 相加 最大 就是 18 进制 只有可能是
add = Math.floor(result / 10);
i -= 1;
j -= 1;
}
return ans.reverse().join('');
}复杂度分析
- 时间复杂度: len1 = num1.length, len2 = num2.length. 竖式加法的次数取决于较大树的位数
- 空间复杂度: O(1) 除答案外我们只需要常数空间存放若干变量。