題目連結(jié):
題目意譯:
一個(gè)「加法數(shù)」為一個(gè)字串,其位數(shù)數(shù)字可以形成一個(gè)「加法序列」。
一個(gè)合法的加法序列應(yīng)包含至少三個(gè)數(shù)字。並且除了前兩個(gè)數(shù)字以外,接下來的序列中每一個(gè)數(shù)字都必須是前兩個(gè)數(shù)字之和。
給定一個(gè)只包含數(shù)字的字串。如果其為一個(gè)加法數(shù),則回傳真(True);反之,則回傳假(False)。
注: 加法序列中的數(shù)字不得包含前導(dǎo)零,所以序列 1, 2, 03 或是 1, 02, 3 是不合法的。
限制:
1 ≦ num.length ≦ 35
num 只包含數(shù)字。
進(jìn)階:在輸入的數(shù)字很大的情況下,你會(huì)怎麼處理溢位之狀況。
範(fàn)例測(cè)資:
範(fàn)例 1:
輸入: "112358"
輸出: true
解釋:
這些位數(shù)可以形成一個(gè)加法序列: 1, 1, 2, 3, 5, 8。
1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8
範(fàn)例 2:
輸入: "199100199"
輸出: true
解釋:
加法序列為: 1, 99, 100, 199。
1 + 99 = 100, 99 + 100 = 199
解題思維:
基本上就是
這題,只是開頭兩個(gè)數(shù)字可以是 long long 型態(tài)而不再限制於 int 範(fàn)圍而已(根據(jù)題目的限制條件)。
至於進(jìn)階的部份,很簡(jiǎn)單,同樣的程式碼(注:範(fàn)例程式碼是用 C++ 寫的)但是改用 Python 或其他內(nèi)建大數(shù)運(yùn)算的語言來寫。除非你想自己寫大數(shù)加法(比起其他運(yùn)算來說這已經(jīng)相當(dāng)簡(jiǎn)單了)。
此次分享到此為止,如有任何更加簡(jiǎn)潔的想法或是有說明不清楚之地方,也煩請(qǐng)各位大大撥冗討論。