刷了一天回溯算法

由于發(fā)現(xiàn)自己遞歸的回溯部分還是不太清楚，今天就特意抽出一整天的時(shí)間來練習(xí)回溯算法。

練習(xí)方式：把《代碼隨想錄》上面第九章回溯算法這一章的所有題目，總共有十四道題目都做了一遍。

32 分鐘前#37 解數(shù)獨(dú)困難2 次

4 小時(shí)前#51 N 皇后困難3 次5 小時(shí)前#47 全排列 II中等1 次5 小時(shí)前#46 全排列中等1 次5 小時(shí)前#491 遞增子序列中等3 次7 小時(shí)前#90 子集 II中等3 次8 小時(shí)前#78 子集中等1 次8 小時(shí)前#93 復(fù)原 IP 地址中等1 次8 小時(shí)前#131 分割回文串中等1 次10 小時(shí)前#40 組合總和 II中等4 次11 小時(shí)前#39 組合總和中等1 次12 小時(shí)前#17 電話號碼的字母組合中等2 次12 小時(shí)前#216 組合總和 III中等1 次12 小時(shí)前#77 組合中等2 次

回顧復(fù)盤一下

77. 組合

這個題以前是直接用python的combination做的，但是總感覺用庫心里不踏實(shí)，沒有學(xué)到精髓。也不利于遞歸思維的提升。所以就看書學(xué)了學(xué)回溯算法。

感覺回溯算法的核心精髓，就是：每次遞歸操作完了之后都會撤銷當(dāng)前操作。，就比如這段代碼里面的 lst.pop()，忽然感覺以前的自己實(shí)在是太屑了。不知道在遍歷決策樹的時(shí)候怎么倒退，干著急也沒辦法，原來就是這么簡單，感覺很妙。

216. 組合總和 III

這個題偷了個懶。感覺和第一題有點(diǎn)相似了。就調(diào)了個庫

17. 電話號碼的字母組合

這個題踩了個坑WA了一下，傳入空字符串的時(shí)候居然回出錯，于是就加了個特殊判斷。

這個題目看了之后夢回小學(xué)時(shí)代，那個時(shí)候我還在用諾基亞。題目就是用一個九鍵手機(jī)，給出一串?dāng)?shù)字，給出所有的能匹配出來的字母，這個題好像和實(shí)際的現(xiàn)實(shí)還不太一樣，因?yàn)楝F(xiàn)實(shí)情況實(shí)際上是想打出一個b，要按兩下2才行。這個只是直接求組合的所有可能了。就是按一下2，abc都有可能了。

想起來以前周賽好像做過一個題，是給出了很長很長一串?dāng)?shù)字，問可能打出多少種字母，那個題的配圖和這個題的配圖居然是一樣的我記得。但是這個題好像感覺不如那個題難，那個題當(dāng)時(shí)是用動態(tài)規(guī)劃來解決的。當(dāng)時(shí)居然還做了快一個小時(shí)，當(dāng)時(shí)那個題的dp遞推式子居然是剛好碰出來的。

39. 組合總和

這個題不一樣的點(diǎn)在于里面的元素可以無限次被選擇。

做到這道題的時(shí)候就感覺自己在22年五月份還是四月份的時(shí)候，也就是刷劍指offer1的時(shí)候，自己當(dāng)時(shí)的很多這種組合問題好像也遇到過，當(dāng)時(shí)就是全用的combination全偷懶做的，一遇到變種，發(fā)現(xiàn)不能偷懶，就不會了，當(dāng)時(shí)就直接抄別人的答案提交了。但是打開這道題的時(shí)候找不到自己的提交記錄了，可能是劍指offer上面的題有重復(fù)的一樣的題，題源地址可能不是一個。

40. 組合總和 II

這個題總是超過時(shí)間限制

這個題的特點(diǎn)是：結(jié)果的每一個組合里可以有重復(fù)的數(shù)字，但是！！所有的結(jié)果里不能有重復(fù)的組合。。。

就是有一個組合 [1, 1, 2] 是合法的，但是不能有兩個 [1, 1, 2]。

這個我和書上的最開始的做法很一致，一上來先拍了序，但是排序之后怎么去重是個大問題，最開始我是直接遍歷所有組合，單純用一個集合放在最外層來去重，但是發(fā)現(xiàn)這樣總是超時(shí)。

其實(shí)應(yīng)該是在遍歷決策樹的時(shí)候，直接用同層重復(fù)數(shù)字來剪枝去重，不僅達(dá)到了去重的效果，而且還達(dá)到大大大大節(jié)省時(shí)間的效果。

這里的同層去重就是在內(nèi)層放一個set，就是剛好在for的外一層的地方。然后先檢測是否在集合里就行了。

131. 分割回文串

判斷一個字符串是不是回文的，直接用python語法糖了。本質(zhì)上都是用的線性的時(shí)間復(fù)雜度。

這個題問的意思是，在一個字符串的各個縫隙位置上放若干個隔板，隔板分割出來的每一個字符串都是回文的。

有多少種放隔板的方式。

我規(guī)定的下標(biāo)是在對應(yīng)i下標(biāo)元素之后，與i+1之間放隔板。

想了想執(zhí)行一次之后就通過了

93. 復(fù)原 IP 地址

這個題是把所有可能的IP地址返回出來，就是不停的加點(diǎn)，和上一個題有點(diǎn)像。

這個題里面有一些特殊情況的處理。

78. 子集

這題就是獲取一個集合的冪集，以前做這個題的時(shí)候我發(fā)現(xiàn)自己是用combination偷懶了。這次好好做一下。

這個做的時(shí)候懵了一下，看了一下書上畫的圖才意識到，原來是在決策樹上每走一步都記錄添加。

這個不是for循環(huán)橫向擴(kuò)展決策樹寬度了。而是一個二叉樹的形狀，要不要當(dāng)前位置了。

90. 子集 II

這個題是變成了集合里有重復(fù)元素了，然后返回冪集。

答案里面可以有 [1, 1, 2] 這樣的子集，但是不能有重復(fù)的子集，就不能有兩個[1, 1, 2]。這又成了去重問題了

這個去重問題也是，先排序，然后再對決策樹同層去重。

491. 遞增子序列

這個題目就如題的名字一樣簡潔，獲得一個數(shù)組的所有的遞增的子序列。因?yàn)檫f增性質(zhì)，所以所有子序列的長度必須是大于等于2的。

這個題也是，發(fā)現(xiàn)得去重，去重就挺麻煩的，發(fā)現(xiàn)是同層去重。

然后記錄答案的時(shí)候，是只要path數(shù)組的長度一旦大于2，就會記錄。

最開始看到這個題我想的是，這不直接來個二重循環(huán)就可以了嗎。后來逝了一下才發(fā)現(xiàn)，不行。因?yàn)槎匮h(huán)里面那一層沒法做到間斷跳躍的選擇。這個題WA了兩次。邊界條件還得處理。

46. 全排列

這個題好像也可以直接調(diào)用itertools里面的全排列直接寫，但是就失去練習(xí)的意義了。所以特意要學(xué)習(xí)一下回溯怎么實(shí)現(xiàn)全排列。

這個決策樹就是一個完整的樹了，像之前的題一樣，左邊深右邊空。

記錄答案的時(shí)候就剛好是path數(shù)組寫滿了的時(shí)候就記錄。

for循環(huán)里面寫的也是，直接遍歷滿，要排除自己。

以前大二的時(shí)候剛做行列式的程序就用到了全排列算法，當(dāng)時(shí)自己不知道python內(nèi)置庫實(shí)現(xiàn)了，就自己瞎搞，搞的代碼又臭又長，空間復(fù)雜度On！，直接生成了一個多叉樹，也根本不會回溯，就無奈又把多叉樹改成了三叉鏈表。增加了指向父親節(jié)點(diǎn)的指針。特別特別麻煩，居然還搞了一下午?，F(xiàn)在看看以前的自己真的好憨憨。但也沒辦法。只是感覺過去的自己學(xué)習(xí)的進(jìn)度和效率低了。

現(xiàn)在看看這個全排列算法，感覺不怎么難。看著這么幾行代碼，居然還感覺有點(diǎn)簡單。

也許我應(yīng)該有這樣一個警醒：當(dāng)我特別想做出一個東西，但是我的算法卡脖子了，然后我硬是去用自己的方法做。雖然可能很有成就感，但是這可能說明我的算法技能和知識有著嚴(yán)重漏洞。

47. 全排列 II

這個題就是在上一個題的基礎(chǔ)上，要給出全排列的序列里面有了重復(fù)的元素了。

這個去重又有點(diǎn)麻煩了。搞了挺長時(shí)間。

遞歸參數(shù)搞了兩個數(shù)組，一個是記錄選擇下標(biāo)的數(shù)組，一個是記錄選擇的元素的數(shù)組，

選擇下標(biāo)的數(shù)組不能重復(fù)選擇，選擇元素的數(shù)組在樹的同層也是要去重的。

51. N 皇后

這個N皇后問題，以前做過，一看提交記錄發(fā)現(xiàn)，竟然恰好是上一年的這個月

提交結(jié)果執(zhí)行用時(shí)內(nèi)存消耗語言提交時(shí)間備注通過72 ms15.3 MBPython32022/06/16 17:10

添加備注




通過996 ms15.8 MBPython32021/06/13 18:03

DFS，減少了搜索范圍




超出時(shí)間限制N/AN/APython32021/06/13 16:26

上一年的今天左右相差了三天，回憶起以前這個題當(dāng)時(shí)搞了好像將近兩個多小時(shí)，這次好像半小時(shí)就搞過了。看來掌握回溯就是好啊。

并且當(dāng)時(shí)的運(yùn)行時(shí)間也好多。

現(xiàn)在寫的時(shí)候，就判斷斜著相撞的時(shí)候，繞了一下。

字符串處理也感覺得心應(yīng)手了。

37. 解數(shù)獨(dú)

這個解數(shù)獨(dú)，以前大一的時(shí)候2020年上半年，也就是剛開始學(xué)python的那半年搞出來過，當(dāng)時(shí)還沒學(xué)算法，還沒學(xué)數(shù)據(jù)結(jié)構(gòu)，就是想搞出來解決數(shù)獨(dú)的問題。當(dāng)時(shí)也還做了框圖。只是沒有用遞歸。做了整整大半天。

后來知道了leetcode，發(fā)現(xiàn)了有解數(shù)獨(dú)這個題，只是沒想到格式居然是字符串格式，太麻煩了，就一直沒做。

今天終于把這個題給解決了。

判斷數(shù)獨(dú)整體是否有效的時(shí)候還是出了點(diǎn)小bug。

整個回溯遞歸的時(shí)候邏輯也遇到了點(diǎn)問題，發(fā)現(xiàn)自己明明寫好了，但是最后好像又全給擦掉了，就用了一個success變量。但是又發(fā)現(xiàn)最后填寫的數(shù)全都變成9了，原來是自己在遞歸for循環(huán)里忘了break了。還是有好多小細(xì)節(jié)問題。

總結(jié)

今天用了整整一天的時(shí)間又彌補(bǔ)了一下以前算法一直欠缺的地方，感覺很有收獲。

這些去重的問題，層間去重和樹枝下去重，書里講的真的挺清楚的。這個書里給出的做題順序也真的不錯。

可能以后有時(shí)間還是要回頭繼續(xù)做這些題，時(shí)間長了可能又會變得生疏。也許一年之后，我又會變成一個更強(qiáng)的自己?；仡^看到自己現(xiàn)在寫的代碼可能還是不夠好。