415. 字符串相加
題目來源：力扣（LeetCode）https://leetcode-cn.com/problems/add-strings
題目
給定兩個字符串形式的非負整數(shù) num1 和num2 ，計算它們的和。
注意：
- num1 和num2 的長度都小于 5100.
- num1 和num2 都只包含數(shù)字 0-9.
- num1 和num2 都不包含任何前導零。
- 你不能使用任何內建 BigInteger 庫坏快， 也不能直接將輸入的字符串轉換為整數(shù)形式。
解題思路
思路：雙指針实胸，模擬
在這里择诈，先說明一下昔逗，題目中注意部分的最后一個钉迷，不能直接將輸入的字符串轉換為整數(shù)至非，這里說的是不能將整個字符串轉換之后進行計算，并非說完全不能使用類型轉換糠聪。
在這里荒椭，使用雙指針的方法，然后模擬加法運算舰蟆，具體的做法及注意如下：
- 定義雙指針 p趣惠、q，分別指向
num1身害，num2末尾信卡； - 定義變量 carry，用以存儲進位题造；
- 開始模擬計算（注意要加上進位），這里相加結果當大于 10 時猾瘸，將結果模 10界赔，然后再將此時的取模結果添加到 ans 頭部；
- 因為 num1 和 num2 的長度可能不等牵触，那么就有可能出現(xiàn)索引溢出的情況淮悼。當出現(xiàn)這種情況時，要將較短的字符串前面添加 0揽思，用以后續(xù)的計算袜腥。
- 循環(huán)計算直至結束，這里要注意進位 carry 是否不為 0钉汗，當 carry 為 1 的情況下羹令，也要將 1 添加到 ans 頭部。
算法的實現(xiàn)過程圖解如下：
圖示
具體的代碼實現(xiàn)如下损痰。
代碼實現(xiàn)
class Solution:
def addStrings(self, num1: str, num2: str) -> str:
# 用以存儲計算結果
ans = ""
# 定義指針分別指向 num1, num2 末尾
p = len(num1) - 1
q = len(num2) - 1
# 存儲進位
carry = 0
# 模擬加法運算
# 這里將 carry 放到條件中福侈，是考慮后續(xù)計算結束后，還有進位卢未，也就是 carry 為 1 的情況
while p >= 0 or q >= 0 or carry:
# 由于有可能出現(xiàn)索引溢出的現(xiàn)象肪凛，
# 當較短的字符串索引溢出時堰汉，要在頭部添加 0，用以后續(xù)計算
elem1 = int(num1[p]) if p >= 0 else 0
elem2 = int(num2[q]) if q >= 0 else 0
# 模擬計算伟墙，注意加上進位
tmp = elem1 + elem2 + carry
# 相加結果可能大于 10
# 計算進位翘鸭，并且就將結果模 10，余數(shù)添加到 ans 頭部
carry = tmp // 10
ans = str(tmp % 10) + ans
# 往前繼續(xù)計算
p -= 1
q -= 1
return ans
實現(xiàn)結果
實現(xiàn)結果
歡迎關注
公眾號 【書所集錄】
