九章演算法 | Facebook 面試題 : 字元串相加

撰文 | JZ

專欄 | 九章演算法

題目描述

給定兩個字元串，代表兩個數字，num1, num2.計算他們的和。返回類型也是一個字元串。

給定的兩個字元串長度小於5000，只包含數字0-9，同時不包含任何的前導0，不允許使用任何的大整數計算庫。n

樣例輸入

num1 = 「5」, num2= 「613」, 返回「618」

演算法分析

本題是簡單的字元串處理+模擬問題。

由於加法的過程是從個位開始向最高位逐位相加，

而數字的個位在字元串的最大位置處(len - 1)，數字的最高位在字元串的0位置處，

所以應該按照兩個字元串的最大位置對齊，

假設兩個字元串的長度分別為len1和len2，

那麼我們應該從len1-1和len2-1開始逆序逐位相加，

每一位的加法應該考慮三個方面：

兩個字元串在該位的數值以及上一位的進位。

需要注意的是兩個字元串長度很可能並不相等，因此我們在處理完能夠對齊的部分之後還需要考慮較長的字元串剩下的部分。

另外還有一個細節需要注意，最後一次加法運算很可能也存在進位1，這時需要單獨把進位1添加到最後的結果中。

參考代碼

更多優質LC答案查詢網址：http://www.jiuzhang.com/solutions/

面試官角度分析

本題思想比較簡單，是字元串模擬加法問題，如果面試者順利給出正確的解法能夠達到hire的程度。