题目
给定两个字符串形式的非负整数 num1 和num2 ,计算它们的和并同样以字符串形式返回。
你不能使用任何內建的用于处理大整数的库(比如 BigInteger), 也不能直接将输入的字符串转换为整数形式。
规则示例
规则
1 <= num1.length, num2.length <= 104
num1 和num2 都只包含数字 0-9
num1 和num2 都不包含任何前导零
示例1
输入:num1 = “11”, num2 = “123”
输出:“134”
示例2
输入:num1 = “456”, num2 = “77”
输出:“533”
示例3
输入:num1 = “0”, num2 = “0”
输出:“0”
解题分析:双指针,竖式加法
这道题规定不能直接将字符串转为整数进行计算,那么我们只能对字符串中的每一位单独进行计算,就好像在使用数学中的加法“竖式加法”,比如
竖式加法
我们在计算竖式加法时,是从右到左依次计算的,每一位计算完成后,会记录一个进位值,如果有进位,该进位值会和下一位一起计算。因此,我们可以用该思路来进行程序计算,两个字符串的索引就像是两个指针,每计算一位后,两个指针都会往左移动
从图中我们可以得到的有用信息:
两个指针 i 和 j 分别从两个字符串的 Length - 1处开始左移
需要一个变量记录进位值
需要一个变量记录结果,结果字符串拼接时要注意左右方向
每一位字符转数字,我们可以不用强转,而是计算字符编码的插值
因为数字字符的编码是连续的,比如 ‘9’ - ‘0’ = 9
解题:双指针,竖式加法
END