算法知識(shí): 三步學(xué)會(huì)所有遞歸
「遞歸」在算法初學(xué)者眼中總是一個(gè)令人頭疼的問(wèn)題
但其實(shí),這種可以將一個(gè)問(wèn)題拆解為多個(gè)重復(fù)子問(wèn)題的算法只要我們掌握了其中的 “套路” ,便可以游刃有余的解決所有遞歸類問(wèn)題。下面我們就開(kāi)始吧~
一、青蛙跳臺(tái)階
我們首先以最簡(jiǎn)單的「青蛙跳」為例子來(lái)拆解遞歸問(wèn)題
劍指 Offer 10- II. 青蛙跳臺(tái)階問(wèn)題【超級(jí)簡(jiǎn)單】
問(wèn)題定義:一只青蛙一次可以跳上1級(jí)臺(tái)階,也可以跳上2級(jí)臺(tái)階。求該青蛙跳上一個(gè) n 級(jí)的臺(tái)階總共有多少種跳法。
第一步:明確遞歸關(guān)系
當(dāng)我們確定了一個(gè)問(wèn)題是可以使用遞歸思想解決的時(shí)候,我們一定可以明確其中的遞歸關(guān)系,即該問(wèn)題的子問(wèn)題之間存在的函數(shù)關(guān)系。在本題中,我們要 求解青蛙跳上一個(gè) n 級(jí)的臺(tái)階總共有多少種跳法;我們知道青蛙一次只可以跳1級(jí)或2級(jí)的臺(tái)階,那么在小蛙跳上第n 級(jí)臺(tái)階的前一步時(shí),小蛙跳上第n 級(jí)臺(tái)階的前一步時(shí),小蛙?一定站在第n-1 級(jí)或第n-2 級(jí)臺(tái)階上。所以如果設(shè)「青蛙跳上一個(gè) n 級(jí)的臺(tái)階」共有 f(n) 種跳法;則我們可以得到其中的函數(shù)關(guān)系為f(n) = f(n-1) + f(n-2)則可以得到函數(shù)
def f(n): return f(n-1) + f(n-2)
第二步:明確遞歸退出條件
做為一個(gè)遞歸函數(shù),其最容易犯的錯(cuò)誤就是一猛子扎進(jìn)死循環(huán)中再也出不來(lái);
為了避免這種情況的發(fā)生,設(shè)定一個(gè)嚴(yán)謹(jǐn)?shù)倪f歸結(jié)束條件是十分必要的。
在本題中我們得到「一只青蛙一次可以跳上1級(jí)臺(tái)階,也可以跳上2級(jí)臺(tái)階」;
可以知道,當(dāng)臺(tái)階數(shù) n 為 1 時(shí),此時(shí)不需要進(jìn)行求解,可以直接知道小蛙?只有一種跳法,一次就可以跳上去。
當(dāng)臺(tái)階數(shù) n 為 2 時(shí),小蛙?可以 一次跳兩個(gè)臺(tái)階 或 一次跳一個(gè)臺(tái)階一共跳兩次,可以有兩種跳法。
則我們可以得到函數(shù)停止條件
def f(n): if n == 1: return 1 if n == 2: return 2 return f(n-1) + f(n-2)
第三步:校驗(yàn)整體邏輯
在上述函數(shù)中顯然,對(duì)于 n ,我們只考慮到了n >= 1的情況;
為了題目更嚴(yán)謹(jǐn)(不僅本題,所有題目都要記得最后校驗(yàn)),我們最后補(bǔ)全可能存在的所有情況;
即根據(jù)算法題命題,最后必須要考慮到的邊界條件。
又因?yàn)轭}目示例中給到:
所以得到最后的函數(shù):
def f(n): if n == 0: return 1 if n == 1: return 1 return f(n-1) + f(n-2)
(當(dāng)然,該題最好的解法是使用動(dòng)態(tài)規(guī)劃方法~ 但我們本篇文章著重在于遞歸思想的拆解,因此暫時(shí)不講這種解法)
想必,前面的內(nèi)容過(guò)于簡(jiǎn)單
大家都已經(jīng)躍躍欲試了吧
接下來(lái),我們使用樹(shù)?的問(wèn)題來(lái)驗(yàn)證這三步方法
二、二叉樹(shù)的最大深度
「樹(shù)?是一種常見(jiàn)的遞歸問(wèn)題的應(yīng)用」
104. 二叉樹(shù)的最大深度【簡(jiǎn)單】
問(wèn)題定義:
讓我們使用剛才的方法,小試牛刀吧~
首先我們要明確樹(shù)的數(shù)據(jù)結(jié)構(gòu)
# class TreeNode(object):# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = right
第一步:明確遞歸關(guān)系
我們想要得到一棵二叉樹(shù)的最大深度,對(duì)于樹(shù)中的一個(gè)node節(jié)點(diǎn)n,我們已知其深度關(guān)系為該節(jié)點(diǎn)的左右孩子的最大深度加一,則我們可得到:def f(n): return max( f(n.left), f(n.right) ) + 1
第二步:明確遞歸退出條件
在本題中我們可以看到,樹(shù)的深度是指最深的葉子節(jié)點(diǎn)到樹(shù)的根節(jié)點(diǎn)之間的距離。因此,我們?cè)谂袛噙f歸的停止條件時(shí),需要考慮葉子節(jié)點(diǎn)的結(jié)束條件。此時(shí)需要明確的是,對(duì)于沒(méi)有左/右孩子的樹(shù)節(jié)點(diǎn)要如何計(jì)算?這里需要我們制定統(tǒng)一的標(biāo)準(zhǔn):我們認(rèn)為所有的 有值節(jié)點(diǎn) 都是有左右孩子的,比如對(duì)于左下角值為15的節(jié)點(diǎn)來(lái)說(shuō),他的左右孩子均為None。然后我們將遞歸結(jié)束條件設(shè)置為:當(dāng) 當(dāng)前節(jié)點(diǎn) 為None時(shí),深度為0。即可得到:
def f(n): if n is None: return 0 return max( f(n.left) , f(n.right) ) + 1
第三步:校驗(yàn)整體邏輯
判斷邊界條件,驗(yàn)證該函數(shù)的輸入節(jié)點(diǎn)為根節(jié)點(diǎn)root時(shí),是否依然符合以上邏輯。
(當(dāng)然,該題目也可以使用深度優(yōu)先遍歷等方法,可以通過(guò)leetcode傳送門去實(shí)戰(zhàn)哦~)
三、滿足條件的最長(zhǎng)子串
395. 至少有 K 個(gè)重復(fù)字符的最長(zhǎng)子串【中等】
問(wèn)題定義:給你一個(gè)字符串 s 和一個(gè)整數(shù) k ,請(qǐng)你找出 s 中的最長(zhǎng)子串, 要求該子串中的每一字符出現(xiàn)次數(shù)都不少于 k 。返回這一子串的長(zhǎng)度。
第一步:明確遞歸關(guān)系
當(dāng)輸入字符串 s 中的某一字符 c 不滿足條件時(shí)(在該字符串 s 中的出現(xiàn)次數(shù)少于 k ),則所求的子串長(zhǎng)度為「不包含字符c的其他的滿足條件的子串長(zhǎng)度」的最大值。
聽(tīng)起來(lái)可能比較繞,其實(shí)拆解出來(lái)就是這樣:比如,對(duì)于輸入字符串 s = "ababcaaabdddcaaa" 并要求出現(xiàn)次數(shù) k=3 來(lái)說(shuō),對(duì)于該字符串中的字符 c ,只出現(xiàn)了一次,所以字符串 s = "ababcaaabdddcaaa" 中滿足條件的子串必然不包含字符 c ;因此,該字符串 s = "ababcaaabdddcaaa" 可以被拆解為 s1 = "abab", s2 = "aaabddd" 與 s3 = "aaa" ;接下來(lái)對(duì)于字符串 s2 = "aaabddd" ,其中的字符b,只出現(xiàn)了一次;因此,字符串 s2 又可以被分為 s21 = "aaa" 與 s2 = "ddd"以此類推...
因此,我們可以得到子串長(zhǎng)度的遞歸關(guān)系為:f(s) = max( f(s1) , f(s2) , f(s...) )
def f(s): for char in set(s): if s.count(char) < k: sub_s_list = s.split(char) return max([f(sub) for sub in sub_s_list])
第二步:明確遞歸退出條件
若不存在這樣的字符 c ,則表明字符串 s 直接滿足該條件,可直接返回字符串 s 的長(zhǎng)度。
def f(s): for char in set(s): if s.count(char) < k: sub_s_list = s.split(char) return max([f(sub) for sub in sub_s_list]) return len(s)
當(dāng)本身字符串 s 的長(zhǎng)度 < k 時(shí),即永遠(yuǎn)不可能有滿足題目要求的子串,所以直接返回0。
def f(s): if len(s) < k: return 0 for char in set(s): if s.count(char) < k: sub_s_list = s.split(char) return max([f(sub) for sub in sub_s_list]) return len(s)
第三步:校驗(yàn)整體邏輯
判斷邊界條件,驗(yàn)證該函數(shù)進(jìn)入遞歸時(shí)的返回結(jié)果 與 未進(jìn)入遞歸時(shí)的返回結(jié)果。
(該題目也可以使用分治法或滑動(dòng)窗口等方法,可以通過(guò)leetcode傳送門去實(shí)戰(zhàn)哦~)
* 本文涉及題目 * :
劍指 Offer 10- II. 青蛙跳臺(tái)階問(wèn)題
104. 二叉樹(shù)的最大深度
395. 至少有 K 個(gè)重復(fù)字符的最長(zhǎng)子串
怎么樣,是不是很簡(jiǎn)單快去試一試更多遞歸問(wèn)題吧

發(fā)表評(píng)論
請(qǐng)輸入評(píng)論內(nèi)容...
請(qǐng)輸入評(píng)論/評(píng)論長(zhǎng)度6~500個(gè)字
最新活動(dòng)更多
-
7月22-29日立即報(bào)名>> 【線下論壇】第三屆安富利汽車生態(tài)圈峰會(huì)
-
7.30-8.1火熱報(bào)名中>> 全數(shù)會(huì)2025(第六屆)機(jī)器人及智能工廠展
-
7月31日免費(fèi)預(yù)約>> OFweek 2025具身智能機(jī)器人產(chǎn)業(yè)技術(shù)創(chuàng)新應(yīng)用論壇
-
免費(fèi)參會(huì)立即報(bào)名>> 7月30日- 8月1日 2025全數(shù)會(huì)工業(yè)芯片與傳感儀表展
-
即日-2025.8.1立即下載>> 《2024智能制造產(chǎn)業(yè)高端化、智能化、綠色化發(fā)展藍(lán)皮書》
-
8月5日立即報(bào)名>> 【在線會(huì)議】CAE優(yōu)化設(shè)計(jì):醫(yī)療器械設(shè)計(jì)的應(yīng)用案例與方案解析
推薦專題
- 1 AI 眼鏡讓百萬(wàn) APP「集體失業(yè)」?
- 2 豆包前負(fù)責(zé)人喬木出軌BP后續(xù):均被辭退
- 3 一文看懂視覺(jué)語(yǔ)言動(dòng)作模型(VLA)及其應(yīng)用
- 4 “支付+”時(shí)代,支付即生態(tài) | 2025中國(guó)跨境支付十大趨勢(shì)
- 5 中國(guó)最具實(shí)力AI公司TOP10
- 6 深圳跑出40億超級(jí)隱形冠軍:賣機(jī)器人年入6.1億,港股上市
- 7 特斯拉Robotaxi上路,馬斯克端上畫了十年的餅
- 8 “AI六小虎”到了下一個(gè)賽點(diǎn)
- 9 AI視頻,攪動(dòng)1.5萬(wàn)億市場(chǎng)
- 10 張勇等人退出阿里合伙人