题目
难度：★★☆☆☆
类型：字符串
给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和。
注意
num1 和num2 的长度都小于 5100.
num1 和num2 都只包含数字 0-9.
num1 和num2 都不包含任何前导零。
你不能使用任何內建 BigInteger 库， 也不能直接将输入的字符串转换为整数形式。
解答
这道题就是让我们实现小学学的多位数的加法运算，与【题目371. 两整数之和类似】，做完这两道题，我们就学会了使用二进制和十进制进行加法计算的流程。我们可以回顾一下两个多位数的加法流程：
-
从最低位开始，两个数对应位的数字相加，如果和超过了十，就向更高位进一位；
-
如果两个数字长度不同，会出现其中一个数字缺失某些较高位的情况，需要把这些缺失的位看作零；
-
直到算到较长数字的最高位为止，并且要考虑进位。
算法上，我们需要注意：
1. 处理字符与数值的关系。数值的计算需要将单个字符转换为对应的数字，这里我们使用ascii码方式，计算任意数字字符num_char的方式为：ord(num_char) - ord('0')，例如字符'0'对应的数字为ord('0')-ord('0')=0；
2. 关于遍历顺序。输入数字按字符串形式给出，我们从最低位向最高位计算，需要将输入字符串做逆序调整（也可以在索引时逆序索引，但是这样比较麻烦）；
3. 关于如何循环。循环的控制条件需要从最低位遍历到两个数中较长的字符串的长度，我们需要考虑输入的两个数字长度不同的情况，因此逆序提取两个数字的对应位时，需要考虑输入数字在这一位上有没有数值，这里根据下标索引与所提取的字符串的长度之间的关系来进行判定，如果其中一个字符串没有这一位，则当前位设置为零，例如"123"和"45"相加，需要遍历到百位，而且两个数字中提取出的百位分别是"1"和"0"；
4. 不要忽略进位的作用。每一位的计算不仅需要两个数字对应位的值，还需要考虑上一步的进位，且当前位的计算结果可能大于10，这时也需要向更高位进位；另外，在循环遍历结束之后，如果仍然有进位，我们还需要把进位添加到更高位上。例如"99"和"1"相加，循环结束后我们需要把十位上的进位"1"放在结果的更高位百位上。
编码如下：
class Solution(object):
def addStrings(self, num1, num2):
"""
:type num1: str
:type num2: str
:rtype: str
"""
num1, num2 = num1[::-1], num2[::-1] # 将输入字符串逆序
len1, len2 = len(num1), len(num2) # 获得字符串长度
res = '' # 初始化结果变量
carry = 0 # 初始化进位
for i in range(max(len1, len2)): # 开始遍历
n1 = ord(num1[i]) - ord('0') if i < len1 else 0 # 取第一个数的当前位
n2 = ord(num2[i]) - ord('0') if i < len2 else 0 # 取第二个数的当前位
s = n1 + n2 + carry # 当前位的计算结果
carry, r = s // 10, s % 10 # 获得余数和进位
res = str(r) + res # 把余数加到当前结果的最高位
if carry: # 如果算完还有进位
res = str(carry) + res # 加到结果最高位
return res # 返回最终结果
如有疑问或建议，欢迎评论区留言~
网友评论