【leetcode那些事】312 連續相加數列
這道題是 leetcode 上難度為 medium 的題目。
Problems - LeetCode
不過，這道題還是非常值得各位一做的，考的是回溯的思想。如果你的腦子裡沒有這個意識，可能這道題還不是很好想。不過，各位想過沒有，你把這道題拿過來的時候，你的大腦是如何一步步地判斷此題需要用回溯呢？首先，這道題的字元串是完整的，也就是說，拆分點沒有告訴你，因此，你需要考慮到所有可能的拆分點，一說到考慮所有，就要往回溯去想了，實現方法自然是遞歸。（有同學問回溯和遞歸的區別是什麼，這是個不錯的問題，我以後可能會寫文章詳細地去講，不過這裡你就先簡單記：回溯是一種演算法思想，而遞歸是編程的實現方法。可以這麼說：回溯用遞歸實現）
題意不難理解，leetcode 的自帶例子如下：
很清楚，拆分點是可變的，只要有一串序列滿足題意就可以了，需要注意的是，題目規定，以 0 開頭的數字是非法的。
在把代碼寫出來前，我們腦子裡可以先去思考一下常式，我們舉一個例子，試著把完整的常式寫出來：
例：1112233558
由於字元串表達數字的間隔不方便，我們可以用一個數組 res 來存儲由當前的拆分點拆出來的字元串，如果不理解這句話沒關係，我們往下看。
nums = 1112233558, res = [1]
res = [1,1]
res = [1,1,1] 不滿足要求，退棧，請搞清楚棧與遞歸之間的關係。（你甚至可以認為他們是一樣的）
res = [1,1,12] 不滿足
res = [1,1,122] 不滿足
res = [1,1,1223] 不滿足
。。。
res = [1,1,12233558] 不滿足
res = [1,11]
res = [1,11,2] 不滿足
res = [1,11,22] 不滿足
res = [1,11,223] 不滿足
。。。
res = [1,11,2233558] 不滿足
res = [1,112]
res = [1,112,2] 不滿足
res = [1,112,23] 不滿足
res = [1,112,233] 不滿足
。。。
res = [1,112,233558] 不滿足
res = [1,1122]
res = [1,1122,3] 不滿足
。。。
res = [1,11223,3]
。。。
res = [1,11223,35]
。。。
res = [1,1122233558]
res = [1]
res = []
res = [11]
res = [11,1]
res = [11,1,2] 不滿足
。。。
res = [11,1,2233558] 不滿足
。。。
res = [11,12]
res = [11,12,2] 不滿足
res = [11,12,23] 滿足，入棧
res = [11,12,23,3] 不滿足
res = [11,11,22,35] 滿足
res = [11,12,23,35,5] 不滿足
res = [11,12,23,35,58] 滿足，return
如果你真的踏踏實實地跟著常式走了一遍，我相信你已經明白了。
不過，遞歸這塊的代碼是稍微有點繞，我們一步步來，首先，我們每次都要判斷，res 的長度是否大於等於3了，一旦滿足這個要求，就要繼續判斷 res[-1] == res[-2] + res[-3] 如果不滿足就要退棧。
因此，我們可以寫：
if len(res) >= 3 and res[-1] != res[-2] + res[-3]: # if not satisfied, return
print(not satisfied)
return False
接著，我們剩餘的字元串沒有了，也就是說都跑到 res 裡面去了，而且通過了上面一個 if，即，res[-1] == res[-2] + res [-3] 也就是滿足題意了，那麼，我們可以就可以返回 True 了，因此，我們可以寫：
if num_str == "" and len(res) >= 3: # help avoid only 2 digit
print(correct until now)
return True
再者，我們則要寫程序最重要的部分，當程序在運行中的時候，也就是還有剩餘的字元串，我們怎麼寫代碼？我們再回過頭看看常式，我們知道了，每次我們都會給上一個不滿足要求的字元串多填一位，然後在試探一下是否滿足要求。同時，我們也要避免，一個數字以 0 為開頭，因此，用一個 for 循環，一個 if，和一個嵌套遞歸就足夠了。
於是我們可以寫：
for i in range(len(num)):
next = num[:i+1]
print(res,res,i,i,next,next)
if (next[0] == 0 and len(next) != 1): # help avoid number starting with 0
print(begin with 0)
continue
if dfs(num[i+1:], res + [int(next)]): # recursive function
return True
是不是仔細看下來的話，這道看似高大上的回溯，也不是很難呢？
推薦閱讀：
TAG:演算法 | 力扣（LeetCode） | Python |