个人网站用react做,wordpress礼物说主题,主机屋vps网站助手,wordpress 时间代码题目描述
以字符串的形式读入两个数字#xff0c;编写一个函数计算它们的和#xff0c;以字符串形式返回。
数据范围#xff1a;s.length,t.length≤100000#xff0c;字符串仅由’0’~‘9’构成 要求#xff1a;时间复杂度 #x1d442;(#x1d45b;)
示例1
输入编写一个函数计算它们的和以字符串形式返回。
数据范围s.length,t.length≤100000字符串仅由’0’~‘9’构成 要求时间复杂度 ()
示例1
输入“1”,“99” 返回值“100” 说明199100
示例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)的时间复杂度要求。
