本文主要是介绍【算法篇】大数加法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)的时间复杂度要求。
这篇关于【算法篇】大数加法JavaScript版的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!