【算法篇】大数加法JavaScript版
题目描述
以字符串的形式读入两个数字，编写一个函数计算它们的和，以字符串形式返回。
数据范围：s.length,t.length≤100000，字符串仅由’0’~‘9’构成
要求：时间复杂度 𝑂(𝑛)
示例1
输入：“1”,“99”
返回值：“100”
说明：1+99=100
示例2
输入：“114514”,“”
返回值：“114514”
解题思路
为了满足时间复杂度O(n)的要求，我们可以从两个字符串的最后一位开始逐位相加，同时考虑进位的情况。以下是使用JavaScript实现的代码：
function addStrings(s, t) {let result = "";let carry = 0; // 进位初始值为0let i = s.length - 1; // 字符串s的索引let j = t.length - 1; // 字符串t的索引// 当两个字符串都没有遍历完或者还有进位时，继续循环while (i >= 0 || j >= 0 || carry > 0) {// 获取当前位的数字，如果索引小于0，表示字符串已经遍历完，用0代替const x = i >= 0 ? parseInt(s[i], 10) : 0;const y = j >= 0 ? parseInt(t[j], 10) : 0;// 计算当前位的和以及进位const sum = x + y + carry;carry = Math.floor(sum / 10); // 整除10得到进位result = (sum % 10) + result; // 取余数加到结果字符串前面// 移动索引i--;j--;}// 返回结果字符串return result;
}// 示例
console.log(addStrings("1", "99")); // "100"
console.log(addStrings("114514", "")); // "114514"
以上代码的工作原理如下：
- 初始化一个空字符串result用于存储结果，以及一个变量carry用于存储进位值。
- 使用两个索引i和j分别指向字符串s和t的末尾。
- 当i或j大于等于0（表示至少有一个字符串还没有遍历完），或者还有进位时，执行循环体。
- 在循环体中，首先获取两个字符串当前位的数字，如果索引小于0，表示该字符串已经遍历完，用0代替。
- 计算当前位的和以及进位，将当前位的和对10取余数加到结果字符串前面，整除10得到进位值。
- 更新索引i和j，使它们向前移动一位。
- 循环结束后，返回结果字符串result。
这种方法的时间复杂度是O(max(m, n))，其中m和n分别是字符串s和t的长度。由于我们只遍历了较长的字符串的长度，所以满足了O(n)的时间复杂度要求。