??腦抽的我上個文章爛尾坏平，又開新坑，锦亦，舶替，，我只能對自己前面開的爛坑說一句：青山不改杠园，綠水長流顾瞪，我們有緣再見！
??這次我想刷一刷算法題（對抛蚁，我又叒叕換目標(biāo)了）陈醒，把常見的基礎(chǔ)算法做一個總結(jié)（千萬別又是起個頭就扔那里不管了，真的是廢人一個了瞧甩。钉跷。。）
??好肚逸，話不多說爷辙，遞歸（Recursion）走起！
- 目錄：
算法：附錄
算法（1）：遞歸
算法（2）：鏈表
算法（3）：數(shù)組
算法（4）：字符串
算法（5）：二叉樹
算法（6）：二叉查找樹
算法（7）：隊列和堆棧（附贈BFS和DFS）
算法（8）：動態(tài)規(guī)劃
算法（9）：哈希表
算法（10）：排序
算法（11）：回溯法
算法（12）：位操作
概念理解：
??首先我們分析一下定義朦促，遞歸是一種使用某種函數(shù)來解決問題的方法（當(dāng)然你可以忽略這句廢話）膝晾，特殊之處便在于該函數(shù)會不斷調(diào)用它自身來作為其子程序。
??那么务冕，如何實現(xiàn)這么一個函數(shù)呢血当？它調(diào)用自己，又是干了些什么呢禀忆？
??這個小技巧便是該遞歸函數(shù)每一次調(diào)用的時候臊旭，它都能將給定的問題變成該問題的子問題，該函數(shù)會不知疲倦的一直調(diào)用它自己（覺得像影分身之術(shù)油湖，但是確切點說的話巍扛，是那種分身又施展影分身術(shù)的 feel...），直到子問題被解決掉乏德，不再產(chǎn)生遞歸為止（所以說撤奸，不是子子孫孫無窮匱哦，遞歸沒有我們的愚公爺爺厲害）喊括。
??所以胧瓜，遞歸函數(shù)是一定存在邊界的，也就是終止條件郑什。在遇到某種情況時府喳，遞歸函數(shù)將不再調(diào)用自身，而是輸出一個結(jié)果（當(dāng)然也可以什么也不輸出蘑拯，直接結(jié)束子程序）钝满。所以寫遞歸函數(shù)的時候兜粘，一定不要忘了寫終止遞歸的條件（個人建議，先寫這些邊界條件弯蚜，后面再寫程序處理邏輯）~
??扯了這么多孔轴，腦中揮散不去的還是大家對我爆喊 “talk is cheap, show me the code！"的場景碎捺，那么路鹰，代碼兄，該你登場了（以下題目均來自LeetCode）~
??附注：建議大家看看問題3收厨，因為提到了一個遞歸經(jīng)常遇到的問題晋柱，重復(fù)計算，而解決重復(fù)計算的方法也很簡單诵叁，加入一個記憶機制（Memoization）雁竞，也就是儲存我們計算過的值即可。
問題1：字符串翻轉(zhuǎn)黎休，要求浓领，O(1)空間復(fù)雜度（看所給的例子輸入，題目應(yīng)該叫列表翻轉(zhuǎn)才更貼切）
例子：
輸入: ['a','b','c']
輸出: ['c','b','a']
解決思路：
1.取出首尾兩個字符势腮，并做交換；
2.遞歸調(diào)用該函數(shù)漫仆，來翻轉(zhuǎn)剩下的子串捎拯。
3.設(shè)計跳出遞歸的邊界條件，這里是begin >= end盲厌，即字符串遍歷完畢署照。
def reverseString(begin, end,s) -> None:
"""
Do not return anything, modify s in-place instead.
"""
if begin >= end:
return
s[begin], s[end] = s[end], s[begin]
reverseString(begin + 1, end - 1, s)
s = ['a','b','c']
reverseString(0, len(s) - 1, s)
print(s)
### output ###
# ['c', 'b', 'a']
問題2：給定一個鏈表，每兩個相鄰的節(jié)點交換位置吗浩，并返回頭節(jié)點建芙。
例子：
輸入鏈表：1->2->3->4
輸出鏈表：2->1->4->3
解決思路：
1.交換前兩個節(jié)點的位置；
2.把剩下的鏈表傳遞給自身懂扼，遞歸調(diào)用禁荸。
3.當(dāng)?shù)诌_鏈表尾部時結(jié)束遞歸。
class ListNode: #定義節(jié)點類
def __init__(self, x):
self.val = x
self.next = None
def swapPairs(head) -> ListNode: #實現(xiàn)功能的遞歸函數(shù)
if head == None or head.next == None:
return head
temp = head.next # 節(jié)點2阀湿，也就是temp赶熟，即為我們所要的head
head.next = swapPairs(temp.next) #將節(jié)點1 和后面的鏈表串拼接,也就是（4->3）
temp.next = head # 將節(jié)點2的后面接上節(jié)點1
return temp #返回節(jié)點2
def printListNode(node): #輔助函數(shù)，打印鏈表
while node:
print(node.val, end=' ')
if node.next:
print('->', end=' ')
node = node.next
print()
if __name__ == '__main__':
head = node = ListNode(1)
for i in range(2,5):
node.next = ListNode(i)
node = node.next
printListNode(head)
ans = swapPairs(head)
printListNode(ans)
問題3：楊輝三角形（聽說你不知道什么是楊輝三角形陷嘴，鏈接附上映砖，送給各位看官）
??在討論這個問題之前，為了讓大家看的更清晰灾挨，我們先提綱挈領(lǐng)一波邑退，在此討論一下兩個概念竹宋，遞推關(guān)系和邊界條件。
??遞推關(guān)系說白了就是問題結(jié)果和子問題的結(jié)果之間的關(guān)系地技，而邊界條件我們前面提到過蜈七，便是遞歸到了終點，問題無法繼續(xù)分解為子問題乓土，可以直接得到答案宪潮。
??那么通過這個例子，大家一起來看看這兩個概念的具現(xiàn)到底是何方神圣把~
??首先趣苏，我們定義一個函數(shù)狡相，，
代表第
行食磕，
代表第
列尽棕，那么，我們可以列出遞歸關(guān)系式：
其次彬伦，再列出邊界條件：
??這樣子滔悉，思路是不是就清晰明了一些了呢？當(dāng)以后遇到復(fù)雜的遞歸問題的時候单绑，可以先嘗試列出遞歸關(guān)系式和邊界條件回官，可以方便我們更清晰的整理思路呦~
當(dāng)然，問題以及代碼如下：
輸入: 5
輸出:
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]
def generate(numRows) -> list:
def helper(i, j):
if j == 0 or j == i:
return 1
return helper(i - 1, j - 1) + helper(i - 1, j)
ans = []
for i in range(0, numRows):
temp = []
for j in range(0, i + 1):
temp.append(helper(i, j))
ans.append(temp)
print(ans)
return ans
if __name__ == '__main__':
generate(5)
??上面我們的helper函數(shù)搂橙，完美的按照邊界條件和遞歸關(guān)系式要求所寫歉提，結(jié)果也是沒有任何問題。但是区转，但是苔巨，但是！各位小伙伴試試把generate(5) 換成generate(30)試試（測測你電腦性能 /斜眼笑）废离？花費的時間多的讓你懷疑人生侄泽，哈哈~ 那么問題來了，到底是什么原因?qū)е碌哪兀?br>
??我們思考一下蜻韭，當(dāng)計算的時候悼尾，我們需要計算
和
，而這兩個都需要計算一次
湘捎，聰明的朋友诀豁，你是不是發(fā)現(xiàn)了問題所在？對窥妇，那就是重復(fù)計算（這個地方一定要加黑加粗舷胜，因為遞歸非常容易遇到這個問題，大家一定要留意才行）！當(dāng)你需要顯示的行數(shù)愈多時烹骨，重復(fù)計算的量就會越大翻伺。
??所以，上面的程序也就逗小孩子玩玩沮焕，實用性幾乎為零（為什么用幾乎吨岭？因為它還能逗小孩子玩玩。所以這里充分體現(xiàn)了作者嚴(yán)謹(jǐn)?shù)淖膽B(tài)度）峦树。那么辣辫，這種問題該如何解決呢？正解魁巩，加入記憶機制急灭，將我們之前計算過的全部儲存下來即可~
??關(guān)門，上代碼谷遂！
def generate(numRows) -> list:
cache = {}
def helper(i, j):
if (i,j) in cache:
return cache[(i,j)]
if j == 0 or j == i:
return 1
result = helper(i - 1, j - 1) + helper(i - 1, j)
cache[(i,j)] = result
return result
ans = []
for i in range(0, numRows):
temp = []
for j in range(0, i + 1):
temp.append(helper(i, j))
ans.append(temp)
print(ans)
return ans
if __name__ == '__main__':
generate(5)
??這個時候葬馋，我們哪怕把5換成500，也是分分鐘的事情肾扰，不畴嘶，秒秒鐘。
問題4：鏈表翻轉(zhuǎn)（又是一道可惡的鏈表題）
例子：
輸入: 1->2->3->4->5
輸出: 5->4->3->2->1
解決思路：
1.遞歸函數(shù)傳遞兩個參數(shù)集晚，head 和 pre窗悯，head 保存的是原來的鏈表，pre 保存的是翻轉(zhuǎn)的鏈表偷拔。
2.在每次遞歸時蟀瞧，從head上取下來一個節(jié)點，然后把 pre 接在該節(jié)點后面条摸。
3.在遞歸到最后時，head 節(jié)點為空铸屉，而 pre 里面則為翻轉(zhuǎn)好的鏈表钉蒲。
class ListNode: #定義節(jié)點類
def __init__(self, x):
self.val = x
self.next = None
def reverseList( head, pre = None):
if not head: return pre
cur, head.next = head.next, pre
return reverseList(cur, head)
def printListNode(node): #輔助函數(shù)，打印鏈表
while node:
print(node.val, end=' ')
if node.next:
print('->', end=' ')
node = node.next
print()
if __name__ == '__main__':
head = node = ListNode(1)
for i in range(2,6):
node.next = ListNode(i)
node = node.next
printListNode(head)
ans = reverseList(head)
printListNode(ans)
問題5：鏈表相加（跟鏈表杠上了）
一個鏈表相當(dāng)于存了一個數(shù)彻坛，如鏈表（2 -> 4 -> 3）相當(dāng)于數(shù)字342顷啼，我們要做的就是把數(shù)讀出來，然后相加昌屉，再將結(jié)果寫成鏈表形式钙蒙。
輸入: (2 -> 4 -> 3) + (5 -> 6 -> 4)
輸出: 7 -> 0 -> 8
解釋: 342 + 465 = 807.
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
self.prev = None
def printListNode(node): #輔助函數(shù)，打印鏈表
while node:
print(node.val, end=' ')
if node.next:
print('->', end=' ')
node = node.next
print()
def addTwoNumbers( l1: ListNode, l2: ListNode) -> ListNode:
def toint(node):
return node.val + 10 * toint(node.next) if node else 0
def tolist(n):
node = ListNode(n % 10)
if n >= 10:
node.next = tolist(n // 10)
return node
return tolist(toint(l1) + toint(l2))
if __name__ == '__main__':
head1 = node1 = ListNode(1)
for i in range(2,10,2):
node1.next = ListNode(i)
node1 = node1.next
printListNode(head1)
ans = addTwoNumbers(head1,head1)
printListNode(ans)
??最后的最后间驮，渴望變成天使躬厌，，竞帽，啊呸扛施，最后的最后鸿捧，我們來分析一下遞歸問題的時間復(fù)雜度和空間復(fù)雜度，這也是一個需要我們下功夫思考的地方疙渣，那么匙奴，Let’s begin！
-
時間復(fù)雜度：
??遞歸問題時間復(fù)雜度可以由一個公式來表示：
??其中妄荔，
為遞歸問題的時間復(fù)雜度泼菌，
表示為該問題共調(diào)用遞歸函數(shù)的次數(shù)（遞歸花時間，一般問題出在這里啦租。重復(fù)計算導(dǎo)致計算機吐血而亡哗伯，GG前，面對電腦前的你刷钢，帶著疑惑和不甘笋颤，向你道出了最后的遺言：“我跟你...咳咳...什么仇什么怨，我如此強大的計算能力内地，咳咳伴澄，精通千萬種高級計算方法，你為什么要...咳咳...要讓我算1+1算到死阱缓？”非凌。這時，你會如何回答荆针？）敞嗡，而
表示單個遞歸函數(shù)的時間復(fù)雜度。很好理解吧~
??在此航背，我給大家列兩個例子喉悴，方便各位理解：
??例子1：我們來一起重溫一下問題1，字符串翻轉(zhuǎn)問題玖媚。每次我們?nèi)〕鰞蓚€字符箕肃，剩下的繼續(xù)調(diào)用遞歸函數(shù)，那么我們需要調(diào)用n/2次（n代表字符串長度）今魔，那么可得勺像。在每個遞歸函數(shù)當(dāng)中，我們只做了一個交換動作错森，
s[begin], s[end] = s[end], s[begin]吟宦，所以時間復(fù)雜度為，那么涩维，該算法的復(fù)雜度便為:
是不是很簡單呢殃姓？
??例子2:大家可以回想一下斐波那契數(shù)列，如果我們用遞歸來表示的話，可以得到如下公式：??看起來辰狡，好像
锋叨，但是！但是宛篇！但是娃磺！他的復(fù)雜度為
!因為當(dāng)它計算到第n個數(shù)時，需要調(diào)用該遞歸函數(shù)共
次叫倍！
??如下圖所示（為了表示方便偷卧，我們在該數(shù)列前面加上一個數(shù)字0），我們要得到f(4)吆倦，那么需要計算f(2)和f(3)听诸，而計算f(3)，我們又需要再算一遍f(2)蚕泽！從圖中可以看出晌梨，通過這種方式計算，調(diào)用遞歸函數(shù)次數(shù)是指數(shù)級上升的须妻！那么仔蝌，當(dāng)你回想問題3當(dāng)中的楊輝三角形時，會不會發(fā)現(xiàn)了什么異曲同工之處荒吏？那么敛惊，如何解決這種指數(shù)爆炸問題，是不是各位老爺也心中有數(shù)了呢绰更？（是的瞧挤，就是加入記憶機制，把之前計算結(jié)果全部保存下來即可~這時你會驚奇的發(fā)現(xiàn)儡湾，時間復(fù)雜度變成了!
斐波那契數(shù)列計算.png
-
空間復(fù)雜度：
??空間復(fù)雜度我們也是分兩部分來考慮特恬，一部分是遞歸相關(guān)的空間，另一部分是非遞歸相關(guān)的空間徐钠。
??遞歸相關(guān)空間：每次調(diào)用遞歸函數(shù)時鸵鸥，計算機都會從一個棧（stack）當(dāng)中給該函數(shù)分配一些空間，如丹皱，當(dāng)該函數(shù)執(zhí)行結(jié)束時，需要返回原先運算的地方宋税，這便需要一塊內(nèi)存來存儲之前中斷的位置（計算機需要該地址摊崭，才知道該函數(shù)執(zhí)行結(jié)束后，從哪里開始下一步運算）杰赛，還有傳遞給該遞歸函數(shù)的參數(shù)呢簸，以及該函數(shù)的局部變量等等，這些都是跟遞歸相關(guān)的空間使用。
??如果只是一個普通的函數(shù)根时，那么當(dāng)他運行完之后瘦赫，該空間就會被釋放，但是對于遞歸調(diào)用來說蛤迎，直到遇到邊界條件之前确虱，所有被調(diào)用到的遞歸函數(shù)占用的空間都不會被釋放，相當(dāng)于每調(diào)用一次遞歸函數(shù)替裆，空間使用是累計增加的校辩。所以如果不注意，便會遇到 “stack overflow”的場景辆童。
??對于問題1當(dāng)中的字符串翻轉(zhuǎn)問題來說宜咒，遞歸函數(shù)里只進行了一步交換元素位置的操作，所以需要的額外空間為
??非遞歸相關(guān)空間：這部分空間指的是不直接跟遞歸相關(guān)的那部分空間使用情況庭砍。諸如全局變量（常儲存在堆（heap）當(dāng)中）场晶，如我們?yōu)榱丝朔貜?fù)計算問題，所加入的記憶機制逗威，還有算法程序的輸入以及輸出數(shù)據(jù)所占用的空間等峰搪。
尾遞歸（Tail Recursion）
??有一種遞歸較為特殊，叫尾遞歸凯旭。在此簡單講解一下：尾遞歸是一種遞歸概耻，其中遞歸調(diào)用是遞歸函數(shù)中的最后一條指令。 并且函數(shù)中應(yīng)該只有一個遞歸調(diào)用罐呼。說白了鞠柄，其他地方不能出現(xiàn)遞歸調(diào)用，只能是最后一句是遞歸調(diào)用嫉柴。那么厌杜，這么搞到底有什么好處呢？大家先來看兩個例子（功能很簡單计螺，列表求和）：
def sum_non_tail_recursion(ls):
"""
:type ls: List[int]
:rtype: int, the sum of the input list.
"""
if len(ls) == 0:
return 0
# not a tail recursion because it does some computation after the recursive call returned.
return ls[0] + sum_non_tail_recursion(ls[1:])
def sum_tail_recursion(ls):
"""
:type ls: List[int]
:rtype: int, the sum of the input list.
"""
def helper(ls, acc):
if len(ls) == 0:
return acc
# this is a tail recursion because the final instruction is a recursive call.
return helper(ls[1:], ls[0] + acc)
return helper(ls, 0)
??第一個便不是尾遞歸夯尽，雖然遞歸調(diào)用只出現(xiàn)了一次且出現(xiàn)在最后一句，即return語句里登馒，但是匙握，該return里面還包含了加法運算，相當(dāng)于是先遞歸調(diào)用陈轿，再計算加法圈纺，然后把該加法結(jié)果返回秦忿。這樣子看蛾娶，最后一步運算確實不是遞歸調(diào)用灯谣。
??那么大家明白了什么是尾遞歸，可能就有疑惑了蛔琅，這么做到底有啥好處胎许，代碼變得略復(fù)雜了，并且還多了個參數(shù)揍愁，那么這么做到底能得到什么呢呐萨？答案就是，極大的降低了空間復(fù)雜度莽囤！各位懵逼的少年谬擦，且聽我慢慢道來：
??從前有座山，山上呢有座廟朽缎，廟里呢惨远，有個老和尚...(此處省略十萬八千字)，于是话肖，琦玉老師對杰諾斯說到北秽，假設(shè)，我們的遞歸函數(shù)為最筒，如果我們的遞歸調(diào)用如下：
??那么正常情況下贺氓，代碼運行結(jié)束前，每次調(diào)用需要開辟一塊空間床蜘，最終需要開辟n塊空間才行辙培。即空間復(fù)雜度為
。但是如果是尾遞歸呢邢锯？我們只需要開辟兩塊空間扬蕊，空間復(fù)雜度驟降為
！
??因為尾遞歸函數(shù)在遞歸結(jié)束時不需要再進行任何計算丹擎，直接將結(jié)果返回給上一層遞歸函數(shù)尾抑，那么也就意味著，遞歸到的時候蒂培，可以直接將返回值送給
再愈，而不是
！那么护戳，當(dāng)我計算完
的時候践磅，
函數(shù)所占用的內(nèi)存便可以釋放掉，無需保留灸异！
??杰諾斯趕緊拿小本本記下來府适，心中想道，這可能就是老師這么強的原因肺樟，我要趕快記下來才行檐春。
??當(dāng)然，還有一點需要提醒一下大家么伯，那就是這種內(nèi)存優(yōu)化是需要看語言的疟暖。C 以及 C++ 都支持尾遞歸的這種優(yōu)化方式，但是據(jù)我所知田柔，Java 和 Python 好像還不行（當(dāng)然不排除以后會支持）俐巴。所以當(dāng)你所使用的語言不支持時，什么尾不尾的硬爆，那都是浮云一片~
總結(jié)：
接下來說三點遞歸算法使用小貼士：
- 毫無疑問欣舵，首先寫下遞歸關(guān)系式。
- 只要有可能缀磕，咱就用記憶機制缘圈。
- 當(dāng)發(fā)生stack overflow 的時候，嘗試使用尾遞歸袜蚕。
附注：
Answer 1. 你向瀕死的計算機冷笑道：“誰讓你只認識 0 和 1 兩個數(shù)呢”瞄勾。
Answer 2. 你掏出了另一臺閃閃發(fā)光的計算機弓柱，“對不起，我有新歡了⌒练酰”
Answer 3. 你語重心長、態(tài)度堅定的說到：“為了實現(xiàn)中華民族偉大復(fù)興萌京⊙媲幔”
各位看官老爺，希望可以不吝賜教狭归，如有不妥之處還望指出~
也熱切希望大家可以給個小贊夭坪，或點個關(guān)注！
在此謝謝各位爺勒~
