題目
難度：★★☆☆☆
類型：字符串
給定兩個字符串形式的非負整數(shù) num1 和num2 ，計算它們的和。
注意
num1 和num2 的長度都小于 5100.
num1 和num2 都只包含數(shù)字 0-9.
num1 和num2 都不包含任何前導零。
你不能使用任何內建 BigInteger 庫， 也不能直接將輸入的字符串轉換為整數(shù)形式。
解答
這道題就是讓我們實現(xiàn)小學學的多位數(shù)的加法運算，與【題目371. 兩整數(shù)之和類似】，做完這兩道題，我們就學會了使用二進制和十進制進行加法計算的流程。我們可以回顧一下兩個多位數(shù)的加法流程：
從最低位開始，兩個數(shù)對應位的數(shù)字相加，如果和超過了十，就向更高位進一位；
如果兩個數(shù)字長度不同，會出現(xiàn)其中一個數(shù)字缺失某些較高位的情況，需要把這些缺失的位看作零；
直到算到較長數(shù)字的最高位為止，并且要考慮進位。
算法上，我們需要注意：
1. 處理字符與數(shù)值的關系。數(shù)值的計算需要將單個字符轉換為對應的數(shù)字，這里我們使用ascii碼方式，計算任意數(shù)字字符num_char的方式為：ord(num_char) - ord('0')，例如字符'0'對應的數(shù)字為ord('0')-ord('0')=0；
2. 關于遍歷順序。輸入數(shù)字按字符串形式給出，我們從最低位向最高位計算，需要將輸入字符串做逆序調整（也可以在索引時逆序索引，但是這樣比較麻煩）；
3. 關于如何循環(huán)。循環(huán)的控制條件需要從最低位遍歷到兩個數(shù)中較長的字符串的長度，我們需要考慮輸入的兩個數(shù)字長度不同的情況，因此逆序提取兩個數(shù)字的對應位時，需要考慮輸入數(shù)字在這一位上有沒有數(shù)值，這里根據(jù)下標索引與所提取的字符串的長度之間的關系來進行判定，如果其中一個字符串沒有這一位，則當前位設置為零，例如"123"和"45"相加，需要遍歷到百位，而且兩個數(shù)字中提取出的百位分別是"1"和"0"；
4. 不要忽略進位的作用。每一位的計算不僅需要兩個數(shù)字對應位的值，還需要考慮上一步的進位，且當前位的計算結果可能大于10，這時也需要向更高位進位；另外，在循環(huán)遍歷結束之后，如果仍然有進位，我們還需要把進位添加到更高位上。例如"99"和"1"相加，循環(huán)結束后我們需要把十位上的進位"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 # 取第一個數(shù)的當前位
n2 = ord(num2[i]) - ord('0') if i < len2 else 0 # 取第二個數(shù)的當前位
s = n1 + n2 + carry # 當前位的計算結果
carry, r = s // 10, s % 10 # 獲得余數(shù)和進位
res = str(r) + res # 把余數(shù)加到當前結果的最高位
if carry: # 如果算完還有進位
res = str(carry) + res # 加到結果最高位
return res # 返回最終結果
如有疑問或建議，歡迎評論區(qū)留言~
