寫給零基礎(chǔ)的前端算法入門指南，摸魚刷一刷【遞歸與回溯篇】
前言
原本打算通過(guò)一篇文章介紹一下，推薦一下自己的刷題方式和刷題路線，得到一些伙伴的反饋：最好還是更加詳細(xì)，面向零基礎(chǔ)，小白這些，還有github訪問速度也是一方面問題，可能圖片都加載不出來(lái)。
因此，我打算分模塊出幾期文章，這樣你只用通過(guò)文章即可了解 Chocolate 同學(xué)整體刷題匯總啦。
希望能夠幫助你的春秋招。打算出的內(nèi)容計(jì)劃安排如下：
??寫給零基礎(chǔ)的前端算法入門指南，摸魚刷一刷【棧與隊(duì)列與鏈表篇】 ??寫給零基礎(chǔ)的前端算法入門指南，摸魚刷一刷【遞歸與回溯篇】（本期已完成??） 
寫給零基礎(chǔ)的前端算法入門指南，摸魚刷一刷【棧與隊(duì)列與鏈表篇】
寫給零基礎(chǔ)的前端算法入門指南，摸魚刷一刷【遞歸與回溯前置基礎(chǔ)篇】
??寫給零基礎(chǔ)的前端算法入門指南，摸魚刷一刷【雙指針與字符串篇】 ??寫給零基礎(chǔ)的前端算法入門指南，摸魚刷一刷【二叉樹篇】 ??寫給零基礎(chǔ)的前端算法入門指南，摸魚刷一刷【動(dòng)態(tài)規(guī)劃DP篇】 ??寫給零基礎(chǔ)的前端算法入門指南，摸魚刷一刷【總結(jié)篇】
算法這一塊到底如何準(zhǔn)備
首先，我來(lái)簡(jiǎn)單介紹一下自己，在校打過(guò) ACM（如果沒聽過(guò)，當(dāng)我沒說(shuō)，因?yàn)闆]有很大價(jià)值的牌牌，鐵牌，參賽證以及證書倒是一堆）
如果你知道 acm，并且參與過(guò)，對(duì)于國(guó)內(nèi)前端（注意是說(shuō)前端）面試的話，應(yīng)該不需要花費(fèi)很長(zhǎng)的刷題時(shí)間，如果大家有想法了解我的 acm 經(jīng)歷的話，這個(gè)后續(xù)我會(huì)考慮在 「B 站發(fā)布一期視頻」。
那么對(duì)于零基礎(chǔ)的小白來(lái)說(shuō)，可能需要花 10-20 天左右時(shí)間來(lái)準(zhǔn)備算法，而對(duì)于非科班來(lái)說(shuō)這個(gè)周期可能會(huì)更長(zhǎng)一點(diǎn)。那么，現(xiàn)在我準(zhǔn)備來(lái)分享我是如何帶你零基礎(chǔ)刷題的。
第一點(diǎn)，不要畏懼算法，理解了其實(shí)就那會(huì)事，或許你還會(huì)喜歡上做題，當(dāng)然，對(duì)于 acm 大佬做的題就另當(dāng)別論了，這篇文章主體與面試水平為準(zhǔn) 第二點(diǎn)，前端對(duì)于算法這一塊的考察相對(duì)來(lái)說(shuō)會(huì)偏簡(jiǎn)單一點(diǎn)，我在春秋招過(guò)程中遇到的筆試題都是一些常見的題目，比如搜索，貪心，簡(jiǎn)單動(dòng)態(tài)規(guī)劃，經(jīng)典排序算法，都是以 leetcode一些簡(jiǎn)單以及中等難度的居多，而這些算法對(duì)于科班來(lái)說(shuō)的話，應(yīng)該在學(xué)校都學(xué)習(xí)過(guò)，比如算法分析與設(shè)計(jì)，數(shù)據(jù)結(jié)構(gòu)與算法這一類課程，那么有這個(gè)基礎(chǔ)，你的刷題時(shí)間又可以進(jìn)行縮短了第三點(diǎn)，既然說(shuō)到要刷題，該如何刷，我在掘金參考了幾個(gè)大佬（文末有參考處），大家都會(huì)推薦分專題來(lái)刷，在這里，我也是非常推薦的，在這里，我希望的是將刷算法題的數(shù)量再減少一點(diǎn)，帶你入門，當(dāng)你刷完這些專題之后，你就有相關(guān)思維能力主動(dòng)去刷題了，而不是很被動(dòng)的去刷，這樣也很方便自己總結(jié)歸納~ 其它，可以參考大佬的文章，這里不再贅述...
一份思維導(dǎo)圖，讓你的刷題路線更簡(jiǎn)單
開門見山地說(shuō)，首先提供一份思維導(dǎo)圖，讓知識(shí)由繁到簡(jiǎn)。
獲取高清PDF，請(qǐng)?jiān)谖⑿殴娞?hào)「小獅子前端」回復(fù)「LeetCode」，一起刷題或者交流可在后臺(tái)回復(fù)「交流」
本倉(cāng)庫(kù)刷題路線參考 ssh （給大佬點(diǎn)贊）
感謝大佬的歸納總結(jié)，原本打算在大佬那里打卡學(xué)習(xí)，后面考慮不太友好，還是自己新建了一個(gè)倉(cāng)庫(kù)打卡學(xué)習(xí)。
其次，本倉(cāng)庫(kù)解題代碼大部分是自己的代碼風(fēng)格，題量也進(jìn)行了拓展，將會(huì)持續(xù)更新下去，何不 star 收藏一下？
倉(cāng)庫(kù)介紹
倉(cāng)庫(kù)地址：https://github.com/Chocolate1999/leetcode-javascript
本倉(cāng)庫(kù)將全程使用的語(yǔ)言是 JavaScript，是一個(gè)純前端刷題路線，對(duì)于前端刷題沒有方向的小伙伴簡(jiǎn)直是福音。解題代碼會(huì)記錄在本倉(cāng)庫(kù)的 Issues 中，會(huì)按照 label進(jìn)行分類。比如想查看 「遞歸與回溯」 分類下的問題，那么選擇標(biāo)簽進(jìn)行篩選即可。
同時(shí)，小伙伴們可以在 Issues 中提交自己的解題代碼，?? 歡迎 Contributing ，可打卡刷題，堅(jiān)持下來(lái)的人最酷！Give a ?? if this project helped you !
刷題路線
下面正式開始我們的刷題之路，給本篇文章來(lái)個(gè)「點(diǎn)贊+在看」，拿出自己心儀的鍵盤，開始！
以下專題順序僅個(gè)人以及面試高頻點(diǎn)來(lái)總結(jié)的刷題方式，大家可以根據(jù)自己的想法來(lái)組合。更多題集請(qǐng)參考本倉(cāng)庫(kù)哈~
遞歸與回溯
784. 字母大小寫全排列
「題目描述」
給定一個(gè)字符串S，通過(guò)將字符串S中的每個(gè)字母轉(zhuǎn)變大小寫，我們可以獲得一個(gè)新的字符串。返回所有可能得到的字符串集合。
示例：
輸入：S = "a1b2"
輸出：["a1b2", "a1B2", "A1b2", "A1B2"]
輸入：S = "3z4"
輸出：["3z4", "3Z4"]
輸入：S = "12345"
輸出：["12345"]
提示：
S 的長(zhǎng)度不超過(guò)12。
S 僅由數(shù)字和字母組成。
「解題思路」
這道題就是遞歸操作，沒有回溯，是一個(gè)挺有意思的題目，在講解思路之前，我先搬運(yùn)一下大佬的圖解，方便我后續(xù)補(bǔ)充。
參考大佬 liweiwei1419 圖解
第一步
第二步
第三步
第四步
第五步
第六步
好了，有了上述圖解之后（還是感謝大佬的圖解，萬(wàn)分感謝orz），我相信明白的已經(jīng)明白了，如果不明白我繼續(xù)解釋。
此題我們只需要從頭往后遍歷一遍即可，對(duì)于非字母節(jié)點(diǎn)，我們只會(huì)產(chǎn)生一個(gè)分支，而對(duì)于字母節(jié)點(diǎn)，我們可以產(chǎn)生兩個(gè)分支，即大寫字母和小寫字母。（詳細(xì)請(qǐng)參見下述代碼）
于是，我們只要簡(jiǎn)單搜一遍就可以了。
/**
* @param {string} S
* @return {string[]}
*/
var letterCasePermutation = function(S) {
let res = []
let dfs = (t,str) => {
if(t.length === S.length)
return res.push(t)
let ch = str[0]
let nextStr = str.substr(1)
// 當(dāng)前位置為數(shù)字，只有一個(gè)分支
if(!isNaN(Number(ch))){
dfs(t+ch,nextStr)
}else{
//當(dāng)前位置為字母，會(huì)產(chǎn)生兩個(gè)分支
let tmp = ch.toUpperCase()
if(tmp === ch) tmp = ch.toLowerCase()
dfs(t+ch,nextStr)
dfs(t+tmp,nextStr)
}
}
dfs('',S)
return res
};
面試題 08.08. 有重復(fù)字符串的排列組合
「題目描述」
有重復(fù)字符串的排列組合。編寫一種方法，計(jì)算某字符串的所有排列組合。
示例1:
輸入：S = "qqe"
輸出：["eqq","qeq","qqe"]
示例2:
輸入：S = "ab"
輸出：["ab", "ba"]
提示:
字符都是英文字母。
字符串長(zhǎng)度在[1, 9]之間。
「解題思路」
全排列，直接用回溯法即可，數(shù)據(jù)量比較小，暴力完事~
var permutation = function (S) {
let res = new Set()
let vis = []
let dfs = (t) => {
if (t.length === S.length) return res.add(t)
for (let i = 0; i < S.length; i++) {
if (vis[i]) continue
vis[i] = true
dfs(t + S[i])
vis[i] = false
}
}
dfs('')
return [...res]
}
980. 不同路徑 III
「題目描述」
在二維網(wǎng)格 grid 上，有 4 種類型的方格：
1 表示起始方格。且只有一個(gè)起始方格。2 表示結(jié)束方格，且只有一個(gè)結(jié)束方格。0 表示我們可以走過(guò)的空方格。-1 表示我們無(wú)法跨越的障礙。返回在四個(gè)方向（上、下、左、右）上行走時(shí)，從起始方格到結(jié)束方格的不同路徑的數(shù)目。
每一個(gè)無(wú)障礙方格都要通過(guò)一次，但是一條路徑中不能重復(fù)通過(guò)同一個(gè)方格。
示例 1：
輸入：[[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
輸出：2
解釋：我們有以下兩條路徑：
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)
示例 2：
輸入：[[1,0,0,0],[0,0,0,0],[0,0,0,2]]
輸出：4
解釋：我們有以下四條路徑：
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2),(2,3)
2. (0,0),(0,1),(1,1),(1,0),(2,0),(2,1),(2,2),(1,2),(0,2),(0,3),(1,3),(2,3)
3. (0,0),(1,0),(2,0),(2,1),(2,2),(1,2),(1,1),(0,1),(0,2),(0,3),(1,3),(2,3)
4. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2),(2,3)
示例 3：
輸入：[[0,1],[2,0]]
輸出：0
解釋：
沒有一條路能完全穿過(guò)每一個(gè)空的方格一次。
請(qǐng)注意，起始和結(jié)束方格可以位于網(wǎng)格中的任意位置。
提示：
1 <= grid.length * grid[0].length <= 20
「解題思路」
回溯算法，不過(guò)這道題需要我們走完所有空格，所以我們起初遍歷的時(shí)候需要統(tǒng)計(jì)一下空格的數(shù)目，然后還有一個(gè)注意點(diǎn)就是重點(diǎn)也算是可走的路徑的一個(gè)點(diǎn)，也需要統(tǒng)計(jì)進(jìn)去，所以代碼 cnt 值 初始化為 1
接下來(lái)就是回溯過(guò)程了，寫了一個(gè) check 函數(shù)，進(jìn)行簡(jiǎn)單判斷剪枝，然后就是往四個(gè)方向搜，每走一個(gè)格子就將當(dāng)前格子設(shè)置為障礙（即 -1），然后搜索完后，回溯時(shí)，需要將障礙重設(shè)置為空格。
/**
* @param {number[][]} grid
* @return {number}
*/
var uniquePathsIII = function(grid) {
let cnt = 1 // 統(tǒng)計(jì)地圖中可走的方格個(gè)數(shù)，包括終點(diǎn)，故初始值為1
let sx,sy // 記錄起點(diǎn)坐標(biāo)
for(let i=0;i<grid.length;i++){
for(let j=0;j<grid[0].length;j++){
if(grid[i][j] === 1){
sx = i
sy = j
}
else if(grid[i][j] === 0){
cnt++
}
}
}
return dfs(sx,sy,cnt,grid)
};
// 剪枝條件
let check = (sx,sy,grid) => {
if(sx<0 || sx>=grid.length || sy<0 || sy>=grid[0].length || grid[sx][sy] == -1) return false
return true
}
let dfs = (sx,sy,cnt,grid) => {
if(!check(sx,sy,grid)) return 0
if(grid[sx][sy] === 2){ // 走到終點(diǎn)時(shí)，也要判斷一下當(dāng)前所有空格是否走完
return cnt === 0 ? 1:0
}
let res = 0
grid[sx][sy] = -1 //走過(guò)的空格進(jìn)行標(biāo)記，設(shè)置為障礙即可
res += dfs(sx+1,sy,cnt-1,grid) // 四個(gè)方向進(jìn)行搜索
res += dfs(sx,sy+1,cnt-1,grid)
res += dfs(sx-1,sy,cnt-1,grid)
res += dfs(sx,sy-1,cnt-1,grid)
grid[sx][sy] = 0 // 回溯過(guò)程，不影響后續(xù)dfs
return res
}
1219. 黃金礦工
「題目描述」
你要開發(fā)一座金礦，地質(zhì)勘測(cè)學(xué)家已經(jīng)探明了這座金礦中的資源分布，并用大小為 m * n 的網(wǎng)格 grid 進(jìn)行了標(biāo)注。每個(gè)單元格中的整數(shù)就表示這一單元格中的黃金數(shù)量；如果該單元格是空的，那么就是 0。
為了使收益最大化，礦工需要按以下規(guī)則來(lái)開采黃金：
每當(dāng)?shù)V工進(jìn)入一個(gè)單元，就會(huì)收集該單元格中的所有黃金。礦工每次可以從當(dāng)前位置向上下左右四個(gè)方向走。每個(gè)單元格只能被開采（進(jìn)入）一次。不得開采（進(jìn)入）黃金數(shù)目為 0 的單元格。礦工可以從網(wǎng)格中 任意一個(gè) 有黃金的單元格出發(fā)或者是停止。
示例 1：
輸入：grid = [[0,6,0],[5,8,7],[0,9,0]]
輸出：24
解釋：
[[0,6,0],
[5,8,7],
[0,9,0]]
一種收集最多黃金的路線是：9 -> 8 -> 7。
示例 2：
輸入：grid = [[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]]
輸出：28
解釋：
[[1,0,7],
[2,0,6],
[3,4,5],
[0,3,0],
[9,0,20]]
一種收集最多黃金的路線是：1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7。
提示：
1 <= grid.length, grid[i].length <= 15
0 <= grid[i][j] <= 100
最多 25 個(gè)單元格中有黃金。
「解題思路」
這題也是搜索相關(guān)，四個(gè)方向，不允許重復(fù)，不過(guò)這次我們需要從不同起點(diǎn)搜索，而且為了減少搜索次數(shù)，我們得從黃金數(shù)量不為0的點(diǎn)開始搜。然后每當(dāng)走不下去的時(shí)候，就比較一下當(dāng)前黃金數(shù)量，求出最大值即可。
/**
* @param {number[][]} grid
* @return {number}
*/
var getMaximumGold = function(grid) {
if(!grid || !grid.length) return 0
let vis = []
// 最終收集的最多黃金數(shù)量
let maxGold = 0
for(let i=0;i<grid.length;i++) vis[i] = []
// 剪枝條件
let check = (x,y) => {
if(x<0 || x>=grid.length || y<0 || y>=grid[0].length || vis[x][y] === 1 || !grid[x][y]) return false
return true
}
let dfs = (x,y,total) => {
if(check(x,y)){
vis[x][y] = 1 //防止重復(fù)
dfs(x+1,y,total+grid[x][y]) // 四個(gè)方向搜索
dfs(x,y+1,total+grid[x][y])
dfs(x-1,y,total+grid[x][y])
dfs(x,y-1,total+grid[x][y])
vis[x][y] = 0
}else{
// 走到底了，就比較一下當(dāng)前黃金數(shù)量
maxGold = Math.max(maxGold,total)
}
}
// 起點(diǎn)從非0單元格開始
for(let i=0;i<grid.length;i++){
for(let j=0;j<grid[0].length;j++){
if(grid[i][j]){
dfs(i,j,0)
}
}
}
return maxGold
};
79. 單詞搜索
「題目描述」
給定一個(gè)二維網(wǎng)格和一個(gè)單詞，找出該單詞是否存在于網(wǎng)格中。
單詞必須按照字母順序，通過(guò)相鄰的單元格內(nèi)的字母構(gòu)成，其中“相鄰”單元格是那些水平相鄰或垂直相鄰的單元格。同一個(gè)單元格內(nèi)的字母不允許被重復(fù)使用。
示例:
board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
給定 word = "ABCCED", 返回 true
給定 word = "SEE", 返回 true
給定 word = "ABCB", 返回 false
提示：
board 和 word 中只包含大寫和小寫英文字母。
1 <= board.length <= 200
1 <= board[i].length <= 200
1 <= word.length <= 10^3
「解題思路」
上一期做了單詞搜索2 hard 版本之后，這道題也想用字典樹玩一玩，沒想到超時(shí)了，后面一想，數(shù)據(jù)確實(shí)有點(diǎn)大，而且對(duì)于一個(gè)單詞來(lái)說(shuō)，建立一顆字典樹豈不是很浪費(fèi)，還要花時(shí)間碼代碼...
本題也是回溯的思路，不過(guò)期間做了一點(diǎn)小優(yōu)化，還是通過(guò)動(dòng)態(tài)更改當(dāng)前所走的格子，省去了那份 開辟vis 數(shù)組的空間。
對(duì)于遞歸層次，由于最后一次計(jì)算時(shí)，層次多算了一次（即多加了一次），所以條件為 >。
var exist = function(grid, word) {
let dfs = (x,y,t) => {
// 最后一次還會(huì) +1 因此，條件是大于
if(t > word.length-1){
return true
}
// 剪枝條件
if(x<0 || x>=grid.length || y<0 || y>=grid[0].length || grid[x][y]!= word[t] || grid[x][y] == '#') return false
let tmp = grid[x][y]
// 開始走
grid[x][y] = '#'
// 從四個(gè)方向搜索，只要一個(gè)方向搜索有結(jié)果，那么直接返回 true即可
let res = dfs(x+1,y,t+1) || dfs(x,y+1,t+1) || dfs(x-1,y,t+1) || dfs(x,y-1,t+1)
if(res) return true
// 回溯（重置）
grid[x][y] = tmp
return false
}
for(let i=0;i<grid.length;i++){
for(let j=0;j<grid[0].length;j++){
if(grid[i][j] == word[0]){
let res = dfs(i,j,0)
if(res) return true
}
}
}
return false
};
212. 單詞搜索 II
「題目描述」
給定一個(gè)二維網(wǎng)格 board 和一個(gè)字典中的單詞列表 words，找出所有同時(shí)在二維網(wǎng)格和字典中出現(xiàn)的單詞。
單詞必須按照字母順序，通過(guò)相鄰的單元格內(nèi)的字母構(gòu)成，其中“相鄰”單元格是那些水平相鄰或垂直相鄰的單元格。同一個(gè)單元格內(nèi)的字母在一個(gè)單詞中不允許被重復(fù)使用。
示例:
輸入:
words = ["oath","pea","eat","rain"] and board =
[
['o','a','a','n'],
['e','t','a','e'],
['i','h','k','r'],
['i','f','l','v']
]
輸出: ["eat","oath"]
說(shuō)明:
你可以假設(shè)所有輸入都由小寫字母 a-z 組成。
提示:
你需要優(yōu)化回溯算法以通過(guò)更大數(shù)據(jù)量的測(cè)試。你能否早點(diǎn)停止回溯？
如果當(dāng)前單詞不存在于所有單詞的前綴中，則可以立即停止回溯。什么樣的數(shù)據(jù)結(jié)構(gòu)可以有效地執(zhí)行這樣的操作？散列表是否可行？為什么？ 前綴樹如何？如果你想學(xué)習(xí)如何實(shí)現(xiàn)一個(gè)基本的前綴樹，請(qǐng)先查看這個(gè)問題： 實(shí)現(xiàn)Trie（前綴樹）。
「解題思路」
「參考力扣官網(wǎng)分析：實(shí)現(xiàn) Trie (前綴樹)」
判斷是否找到了，通過(guò)傳遞節(jié)點(diǎn)的END來(lái)判斷
判斷是否重復(fù)訪問，通過(guò)動(dòng)態(tài)更改走過(guò)的網(wǎng)格點(diǎn)來(lái)判斷，就不需要再定義一個(gè)
vis數(shù)組了
「參考大佬：秦時(shí)明月字典樹建樹解法（二）」
var findWords = function(grid, words) {
// 存放最終結(jié)果集
let res = []
// 字典樹節(jié)點(diǎn)
class TrieNode {
constructor(){
this.end = false
this.child = {}
}
}
// 最終形成的字典樹根節(jié)點(diǎn)
let root = null
let Trie = function(){
root = new TrieNode()
}
// 建立字典樹
Trie.prototype.insert = (word) => {
let cur = root
for(let i=0;i<word.length;i++){
if(!cur.child[word[i]]){
cur.child[word[i]] = new TrieNode()
}
cur = cur.child[word[i]]
}
cur.end = true
}
// 創(chuàng)建根節(jié)點(diǎn)
let trie = new Trie()
// 進(jìn)行建樹操作
for(let i=0;i<words.length;i++){
trie.insert(words[i])
}
let dfs = (x,y,t,cur) => {
if(cur.end){
res.push(t)
cur.end = false // 避免重復(fù)計(jì)算
}
// 剪枝條件：1.邊界處理 2.下一步是否可走 3.下一步字典樹是否可走
if(x<0 || x>=grid.length || y<0 || y>=grid[0].length || grid[x][y] == '#' || !cur.child[grid[x][y]]) return
let tmp = grid[x][y]
grid[x][y] = '#' // 走
cur = cur.child[tmp]
dfs(x+1,y,t+tmp,cur) // 上下左右四個(gè)方向遍歷
dfs(x,y+1,t+tmp,cur)
dfs(x-1,y,t+tmp,cur)
dfs(x,y-1,t+tmp,cur)
grid[x][y] = tmp // 回溯（還原）
}
// 對(duì)單詞表進(jìn)行全局搜索
for(let i=0;i<grid.length;i++){
for(let j=0;j<grid[0].length;j++){
dfs(i,j,'',root)
}
}
return res
};
附上完整字典樹（前綴樹）模板，日后可用~
「在 Trie 樹中查找鍵」
每個(gè)鍵在 trie 中表示為從根到內(nèi)部節(jié)點(diǎn)或葉的路徑。我們用第一個(gè)鍵字符從根開始，。檢查當(dāng)前節(jié)點(diǎn)中與鍵字符對(duì)應(yīng)的鏈接。有兩種情況：
存在鏈接。我們移動(dòng)到該鏈接后面路徑中的下一個(gè)節(jié)點(diǎn)，并繼續(xù)搜索下一個(gè)鍵字符。 不存在鏈接。若已無(wú)鍵字符，且當(dāng)前結(jié)點(diǎn)標(biāo)記為 isEnd，則返回true。否則有兩種可能，均返回false: 還有鍵字符剩余，但無(wú)法跟隨Trie樹的鍵路徑，找不到鍵。沒有鍵字符剩余，但當(dāng)前結(jié)點(diǎn)沒有標(biāo)記為isEnd。也就是說(shuō)，待查找鍵只是Trie樹中另一個(gè)鍵的前綴。
「查找 Trie 樹中的鍵前綴」
該方法與在 Trie 樹中搜索鍵時(shí)使用的方法非常相似。我們從根遍歷 Trie 樹，直到鍵前綴中沒有字符，或者無(wú)法用當(dāng)前的鍵字符繼續(xù) Trie 中的路徑。與上面提到的“搜索鍵”算法唯一的區(qū)別是，到達(dá)鍵前綴的末尾時(shí)，總是返回 true。我們不需要考慮當(dāng)前 Trie 節(jié)點(diǎn)是否用 “isend” 標(biāo)記，因?yàn)槲覀兯阉鞯氖擎I的前綴，而不是整個(gè)鍵。
var findWords = function(grid, words) {
// 存放最終結(jié)果集
let res = []
// 字典樹節(jié)點(diǎn)
class TrieNode {
constructor(){
this.end = false
this.child = {}
}
}
// 最終形成的字典樹根節(jié)點(diǎn)
let root = null
let Trie = function(){
root = new TrieNode()
}
// 建立字典樹
Trie.prototype.insert = (word) => {
let cur = root
for(let i=0;i<word.length;i++){
if(!cur.child[word[i]]){
cur.child[word[i]] = new TrieNode()
}
cur = cur.child[word[i]]
}
cur.end = true
}
// 在 Trie 樹中查找鍵
let searchPrefix = (word) => {
let cur = root
for(let i=0;i<word.length;i++){
if(cur.child[word[i]]){
cur = cur.child[word[i]]
}else{
return null
}
}
return cur
}
Trie.prototype.search = (word) => {
let cur = searchPrefix(word)
return cur !== null && cur.end
}
// 查找 Trie 樹中的鍵前綴
Trie.prototype.startsWith = (pre) => {
return searchPrefix(pre) != null
}
// 創(chuàng)建根節(jié)點(diǎn)
let trie = new Trie()
// 進(jìn)行建樹操作
for(let i=0;i<words.length;i++){
trie.insert(words[i])
}
let dfs = (x,y,t,cur) => {
if(cur.end){
res.push(t)
cur.end = false // 避免重復(fù)計(jì)算
}
// 剪枝條件：1.邊界處理 2.下一步是否可走 3.下一步字典樹是否可走
if(x<0 || x>=grid.length || y<0 || y>=grid[0].length || grid[x][y] == '#' || !cur.child[grid[x][y]]) return
let tmp = grid[x][y]
grid[x][y] = '#' // 走
cur = cur.child[tmp]
dfs(x+1,y,t+tmp,cur) // 上下左右四個(gè)方向遍歷
dfs(x,y+1,t+tmp,cur)
dfs(x-1,y,t+tmp,cur)
dfs(x,y-1,t+tmp,cur)
grid[x][y] = tmp // 回溯（還原）
}
// 對(duì)單詞表進(jìn)行全局搜索
for(let i=0;i<grid.length;i++){
for(let j=0;j<grid[0].length;j++){
dfs(i,j,'',root)
}
}
return res
};
77. 組合
「題目描述」
給定兩個(gè)整數(shù) n 和 k，返回 1 ... n 中所有可能的 k 個(gè)數(shù)的組合。
示例:
輸入: n = 4, k = 2
輸出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
「解題思路」
直接套用組合題解題模板即可
var combine = function (n, k) {
let res = [];
let dfs = (t, start) => {
if (t.length === k) {
res.push(t);
return;
}
for (let i = start; i <= n; i++) {
t.push(i);
dfs(t.slice(), i + 1);
t.pop();
}
}
dfs([], 1);
return res;
};
39. 組合總和
「題目描述」
給定一個(gè)無(wú)重復(fù)元素的數(shù)組 candidates 和一個(gè)目標(biāo)數(shù) target ，找出 candidates 中所有可以使數(shù)字和為 target 的組合。
candidates 中的數(shù)字可以無(wú)限制重復(fù)被選取。
說(shuō)明：
所有數(shù)字（包括 target）都是正整數(shù)。
解集不能包含重復(fù)的組合。
示例 1：
輸入：candidates = [2,3,6,7], target = 7,
所求解集為：
[
[7],
[2,2,3]
]
示例 2：
輸入：candidates = [2,3,5], target = 8,
所求解集為：
[
[2,2,2,2],
[2,3,3],
[3,5]
]
提示：
1 <= candidates.length <= 30
1 <= candidates[i] <= 200
candidate 中的每個(gè)元素都是獨(dú)一無(wú)二的。
1 <= target <= 500
「解題思路」
這道題是組合題，但是這道題有意思的是當(dāng)前元素可以重復(fù)無(wú)限制選取，那么我們可以改一下另外一道組合題的思路，下一層也從 i開始即可，然后本題元素重復(fù)，那么我們不需要進(jìn)行排序然后剪枝了。
// 當(dāng)前元素可以無(wú)限制選取，下一層也從i開始取
dfs(t.slice(),i,sum+candidates[i]);
「參考xiao_ben_zhu圖解」
var combinationSum = function(candidates, target) {
let res = [];
let dfs = (t,start,sum) => {
if(sum >= target){ // 防止爆掉
if(sum === target){
res.push(t);
}
return;
}
for(let i=start;i<candidates.length;i++){
t.push(candidates[i]);
// 當(dāng)前元素可以無(wú)限制選取，下一層也從i開始取
dfs(t.slice(),i,sum+candidates[i]);
t.pop();
}
}
dfs([],0,0);
return res;
};
40. 組合總和 II
「題目描述」
給定一個(gè)數(shù)組 candidates和一個(gè)目標(biāo)數(shù) target ，找出candidates 中所有可以使數(shù)字和為target的組合。
candidates中的每個(gè)數(shù)字在每個(gè)組合中只能使用一次。
說(shuō)明：
所有數(shù)字（包括目標(biāo)數(shù)）都是正整數(shù)。解集不能包含重復(fù)的組合。示例 1:
輸入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集為:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
示例 2:
輸入: candidates = [2,5,2,1,2], target = 5,
所求解集為:
[
[1,2,2],
[5]
]
「解題思路」
這道題也是一道組合題，但是這道題數(shù)組里面是存在重復(fù)元素的，組合題的話，為了更好地去重，我們可以先對(duì)數(shù)組進(jìn)行排序，然后對(duì)于每一層如果相鄰元素相同，就剪掉該分支即可。
「參考xiao_ben_zhu大佬圖解」
注意求和那里，如果只判斷是否相等的話，可能會(huì)出現(xiàn)爆掉情況。
var combinationSum2 = function (candidates, target) {
let res = [];
candidates.sort((a, b) => a - b);
let dfs = (t, start, sum) => {
if (sum >= target) { // 加這外層，超出范圍了也終止，防爆棧
if (sum === target) {
res.push(t);
}
return;
}
// 組合
for (let i = start; i < candidates.length; i++) {
// 組合元素不能重復(fù)，去掉同一層重復(fù)的元素
if (i > start && candidates[i] == candidates[i - 1]) continue;
t.push(candidates[i]);
// 組合元素去重，即當(dāng)前選擇和下一層的不能重復(fù)
dfs(t.slice(), i + 1, sum + candidates[i]);
t.pop();
}
}
dfs([], 0, 0);
return res;
};
216. 組合總和 III
「題目描述」
找出所有相加之和為 n 的 k 個(gè)數(shù)的組合。組合中只允許含有 1 - 9 的正整數(shù)，并且每種組合中不存在重復(fù)的數(shù)字。
說(shuō)明：
所有數(shù)字都是正整數(shù)。解集不能包含重復(fù)的組合。示例 1:
輸入: k = 3, n = 7
輸出: [[1,2,4]]
示例 2:
輸入: k = 3, n = 9
輸出: [[1,2,6], [1,3,5], [2,3,4]]
「解題思路」
首先，還是搬運(yùn)一下大佬的圖解，然后我再來(lái)解釋一番。
「參考xiao_ben_zhu大佬圖解」
本題需要一層一層來(lái)，第一層我們可以有 i(1-9)個(gè)選擇，而第二層的每一個(gè)值只有 i+1個(gè)選擇了，因?yàn)椴荒苤貜?fù)。比如你第一次拿了 2，在下一次，你只能從 3開始拿了，如果還是 1的話就會(huì)有重復(fù)的組合了。這樣我們也不用維護(hù) vis數(shù)組來(lái)去重，因?yàn)槊恳粚尤〉闹凳遣灰粯拥摹?/p>
var combinationSum3 = function (k, n) {
let res = [];
let dfs = (t, start, sum) => {
if (t.length === k && sum === n) {
res.push(t);
}
for (let i = start; i < 10; i++) {
t.push(i);
dfs(t.slice(), i + 1, sum + i);
t.pop();
}
}
dfs([], 1, 0);
return res;
};
401. 二進(jìn)制手表
「題目描述」
二進(jìn)制手表頂部有 4 個(gè) LED 代表 「小時(shí)（0-11）」，底部的 6 個(gè) LED 代表 「分鐘（0-59）」。
每個(gè) LED 代表一個(gè) 0 或 1，最低位在右側(cè)。
例如，上面的二進(jìn)制手表讀取 “3:25”。
給定一個(gè)非負(fù)整數(shù) n 代表當(dāng)前 LED 亮著的數(shù)量，返回所有可能的時(shí)間。
示例：
輸入: n = 1
返回: ["1:00", "2:00", "4:00", "8:00", "0:01", "0:02", "0:04", "0:08", "0:16", "0:32"]
提示：
輸出的順序沒有要求。
小時(shí)不會(huì)以零開頭，比如 “01:00” 是不允許的，應(yīng)為 “1:00”。
分鐘必須由兩位數(shù)組成，可能會(huì)以零開頭，比如 “10:2” 是無(wú)效的，應(yīng)為 “10:02”。
超過(guò)表示范圍（小時(shí) 0-11，分鐘 0-59）的數(shù)據(jù)將會(huì)被舍棄，也就是說(shuō)不會(huì)出現(xiàn) "13:00", "0:61" 等時(shí)間。
「解題思路」
回溯算法，我的解法類似于全排列做法，將10個(gè)小燈泡進(jìn)行排列組合，然后根據(jù) 0 和 1 來(lái)判斷燈泡是否亮，如果亮了，加上對(duì)應(yīng)二進(jìn)制，然后將 0-3分給小時(shí)來(lái)計(jì)算，將 4-9分給分鐘來(lái)計(jì)算，但是要考慮一下，就是可能會(huì)出現(xiàn)重復(fù)情況，于是用 Set數(shù)據(jù)結(jié)構(gòu)維護(hù)一下就好了。
var readBinaryWatch = function(num) {
let res = new Set();
let vis = new Array(10).fill(0)
let check = (hour,minutes) => {
if(hour>=0 && hour<=11 && minutes>=0 && minutes<=59) return true;
return false;
}
let dfs = (t,vis) => {
if(t==0){
let hour = vis[0]*1 + vis[1]*2 + vis[2]*4 + vis[3]*8;
let minutes = vis[4]*1 + vis[5]*2 + vis[6]*4 + vis[7]*8 + vis[8]*16 + vis[9]*32;
if(check(hour,minutes)){
let tmp = `${hour}:${minutes >= 10? minutes: '0'+minutes}`;
res.add(tmp);
}
}
for(let i=0;i<10;i++){
if(vis[i]) continue;
vis[i] = 1;
dfs(t-1,vis);
vis[i] = 0;
}
}
dfs(num,vis);
return [...res];
};
補(bǔ)充，后面看到有大佬這樣做，進(jìn)行了去重操作，關(guān)鍵點(diǎn)在回溯 for循環(huán)那里。其實(shí)這個(gè)相當(dāng)于全排列了。
var readBinaryWatch = function(num) {
let res = [];
let vis = new Array(10).fill(0)
let check = (hour,minutes) => {
if(hour>=0 && hour<=11 && minutes>=0 && minutes<=59) return true;
return false;
}
let dfs = (t,cnt,vis) => {
if(t==0){
let hour = vis[0]*1 + vis[1]*2 + vis[2]*4 + vis[3]*8;
let minutes = vis[4]*1 + vis[5]*2 + vis[6]*4 + vis[7]*8 + vis[8]*16 + vis[9]*32;
if(check(hour,minutes)){
let tmp = `${hour}:${minutes >= 10? minutes: '0'+minutes}`;
res.push(tmp);
}
return;
}
for(let i=cnt;i<=10-t;i++){
if(vis[i]) continue;
vis[i] = 1;
dfs(t-1,i+1,vis);
vis[i] = 0;
}
}
dfs(num,0,vis);
return res;
};
37. 解數(shù)獨(dú)
「題目描述」
編寫一個(gè)程序，通過(guò)填充空格來(lái)解決數(shù)獨(dú)問題。
一個(gè)數(shù)獨(dú)的解法需「遵循如下規(guī)則」：
數(shù)字 1-9 在每一行只能出現(xiàn)一次。數(shù)字 1-9 在每一列只能出現(xiàn)一次。數(shù)字 1-9 在每一個(gè)以粗實(shí)線分隔的 3x3 宮內(nèi)只能出現(xiàn)一次。空白格用 '.' 表示。
一個(gè)數(shù)獨(dú)。
答案被標(biāo)成紅色。
提示：
給定的數(shù)獨(dú)序列只包含數(shù)字 1-9 和字符 '.' 。
你可以假設(shè)給定的數(shù)獨(dú)只有唯一解。
給定數(shù)獨(dú)永遠(yuǎn)是 9x9 形式的。
「解題思路」
我們一行一行的放，如果能得到一個(gè)解，直接返回 true，然后剪枝條件如下述 check函數(shù)。
「參考xiao_ben_zhu大佬圖解」
var solveSudoku = function (board) {
let check = (x, y, val) => {
// 一行或者一列有重復(fù)元素，剪掉
for (let i = 0; i < 9; i++) {
if (board[x][i] == val || board[i][y] == val) return true;
}
let xx = Math.floor(x / 3) * 3;
let yy = Math.floor(y / 3) * 3;
// 3x3宮格內(nèi)重復(fù)的情況，剪掉
for (let i = 0; i < 3; i++) {
for (let j = 0; j < 3; j++) {
if (board[xx + i][yy + j] == val) return true;
}
}
return false; // 沒有沖突情況
}
let dfs = (x, y) => {
if (y == 9) {
x++;
y = 0;
if (x == 9) return true; // 都填完了，直接返回 true
}
if (board[x][y] != '.') return dfs(x, y + 1);
for (let i = 1; i < 10; i++) {
if (check(x, y, String(i))) continue;
board[x][y] = String(i);
if (dfs(x, y + 1)) return true; // 如果往下走，能夠解出數(shù)獨(dú)，直接返回 true
board[x][y] = '.'; // 回溯，因?yàn)橥伦叩貌坏揭粋€(gè)解
}
return false;
}
dfs(0, 0);
return board;
};
51. N 皇后
「題目描述」
n 皇后問題研究的是如何將 n 個(gè)皇后放置在 n×n 的棋盤上，并且使皇后彼此之間不能相互攻擊。
上圖為 8 皇后問題的一種解法。
給定一個(gè)整數(shù) n，返回所有不同的 n 皇后問題的解決方案。
每一種解法包含一個(gè)明確的 n 皇后問題的棋子放置方案，該方案中 'Q' 和 '.' 分別代表了皇后和空位。
示例：
輸入：4
輸出：[
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],
["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]
解釋: 4 皇后問題存在兩個(gè)不同的解法。
提示：
皇后彼此不能相互攻擊，也就是說(shuō)：任何兩個(gè)皇后都不能處于同一條橫行、縱行或斜線上。
「解題思路」
對(duì)于 n 皇后問題，經(jīng)典的回溯算法，我們采用一行放一個(gè)，然后逐行來(lái)放，這樣我們就不用在剪枝的時(shí)候判斷是否同行了。只需要判斷是否同列 或者 同一斜線就好了。
參考「xiao_ben_zhu」大佬圖解
var solveNQueens = function(n) {
let res = [];
let grid = new Array(n); // 初始化一個(gè)地圖
for(let i=0;i<n;i++){
grid[i] = new Array(n).fill('.');
}
// 剪枝條件
let check = (x,y)=>{
for(let i=0;i<x;i++){
for(let j=0;j<n;j++){
// 判斷同列 或者 同一斜線即可（不需要判斷同行是因?yàn)橐恍幸恍蟹诺?，一定不同行?/span>
if(grid[i][j] == 'Q' && (j == y || i+j == x+y || i-j == x-y) ){
return true;
}
}
}
return false;
}
let dfs = (t) => {
if(t === n ){
let ans = grid.slice(); // 拷貝一份，對(duì)輸出做處理
for(let i=0;i<n;i++){
ans[i] = ans[i].join('');
}
res.push(ans);
return;
}
for(let i=0;i<n;i++){
if(check(t,i)) continue;
grid[t][i] = 'Q';
dfs(t+1);
grid[t][i] = '.';
}
}
dfs(0);
return res;
};
131. 分割回文串
「題目描述」
給定一個(gè)字符串 s，將 s 分割成一些子串，使每個(gè)子串都是回文串。
返回 s 所有可能的分割方案。
示例:
輸入: "aab"
輸出:
[
["aa","b"],
["a","a","b"]
]
「解題思路」
借鑒「zesong-wang-c」 大佬的圖解
本題采用回溯思想，看上圖基本已經(jīng)明白，每次進(jìn)行一次切割，直到切到最后一個(gè)元素，然后壓入結(jié)果集合里，期間對(duì)于每次切割的字符串，我們判斷一下是否是回文，如果不是，直接減掉即可。
和組合的思想有點(diǎn)類似。
// 判斷是否是回文
function isPal(str) {
let len = Math.floor(str.length / 2);
if (len === 0) {
return true;
}
let add = str.length % 2 === 0 ? 0 : 1;
let subStr = str.slice(0, len);
for (let i = 0; i < len; i++) {
if (subStr[len - i - 1] !== str[len + add + i]) {
return false;
}
}
return true;
}
var partition = function (s) {
let res = [];
let dfs = (cur, start) => {
// 當(dāng)前已經(jīng)到達(dá)了最后一個(gè)元素
if (start >= s.length) {
res.push(cur.slice());
return;
}
for (let i = start; i < s.length; i++) {
// 字符串切割
let str = s.slice(start, i + 1);
if (str && isPal(str) ) {
cur.push(str);
dfs(cur, i + 1);
// 回溯
cur.pop();
}
}
}
dfs([], 0);
return res;
};
93. 復(fù)原IP地址
「題目描述」
給定一個(gè)只包含數(shù)字的字符串，復(fù)原它并返回所有可能的 IP 地址格式。
有效的 IP 地址 正好由四個(gè)整數(shù)（每個(gè)整數(shù)位于 0 到 255 之間組成，且不能含有前導(dǎo) 0），整數(shù)之間用 '.' 分隔。
例如："0.1.2.201" 和 "192.168.1.1" 是 有效的 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "[email protected]" 是 無(wú)效的 IP 地址。
示例 1：
輸入：s = "25525511135"
輸出：["255.255.11.135","255.255.111.35"]
示例 2：
輸入：s = "0000"
輸出：["0.0.0.0"]
示例 3：
輸入：s = "1111"
輸出：["1.1.1.1"]
示例 4：
輸入：s = "010010"
輸出：["0.10.0.10","0.100.1.0"]
示例 5：
輸入：s = "101023"
輸出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
提示：
0 <= s.length <= 3000
s 僅由數(shù)字組成
「解題思路」
直接看圖解，顯然要用回溯來(lái)做，我的做法是對(duì)于當(dāng)前位置，我們可以有三種選擇，選一個(gè)，選兩個(gè)，還有選三個(gè)。此時(shí)就需要判斷一下是不是會(huì)出現(xiàn)選出邊界的情況。
然后對(duì)于我們選擇的數(shù)字，要判斷是否出現(xiàn)前導(dǎo) 0 ，同時(shí)也要看一下如果是三位數(shù)字的話，是不是會(huì)超過(guò) 255 。題目不能重復(fù)選擇，于是用組合思想，免去 vis 數(shù)組。
借助大佬 xiao_ben_zhu 圖解
var restoreIpAddresses = function (s) {
let res = [];
let dfs = (cur, start) => {
if (cur.length == 4 && start>=s.length) {
res.push(cur.join('.'));
return;
}
if(cur.length == 4 && start != s.length) return;
for(let k=1;k<=3;k++){
// 如果取的范圍超過(guò)了字符串長(zhǎng)度，直接剪掉
if(start+k-1>=s.length) return;
// 切割字符串
let str = s.substring(start,start+k);
if(str.length>=2 && str[0] == 0) return;
if(str.length>=3 && +str > 255) return;
cur.push(str);
dfs(cur.slice(),start+k);
// 回溯
cur.pop();
}
}
dfs([], 0);
return res;
};
22. 括號(hào)生成
「題目描述」
數(shù)字 n 代表生成括號(hào)的對(duì)數(shù)，請(qǐng)你設(shè)計(jì)一個(gè)函數(shù)，用于能夠生成所有可能的并且 有效的 括號(hào)組合。
示例：
輸入：n = 3
輸出：[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
「解題思路」
這道題，看了大佬的題解，發(fā)現(xiàn)真是有意思，現(xiàn)在來(lái)解釋一下。
我們可以直接走可行的情況，對(duì)于不可行的情況，自然就剪掉了。
關(guān)鍵在于左右括號(hào)如何選擇，首先，對(duì)于左括號(hào)，起初我們必然是要選的，然后我們也可以全部選完，因此，只要有左括號(hào)我們必須選，而對(duì)于右括號(hào)而言，它的剩余數(shù)量必須大于剩余左括號(hào)數(shù)量，我們才能選右括號(hào)。
舉個(gè)反例，假如我們現(xiàn)在已經(jīng)有了 (())，n = 3，然后左右括號(hào)都還剩一個(gè)，如果理解選 )，豈不是就 (()))了，顯示不是有效的括號(hào)，應(yīng)該被剪掉才是，因此，我們必須嚴(yán)格右括號(hào)剩余數(shù)量必須大于剩余左括號(hào)數(shù)量，我們才能選右括號(hào)。
參考 笨豬爆破組 大佬圖解
var generateParenthesis = function (n) {
let res = [];
let dfs = (cur, left, right) => {
if (cur.length === 2 * n) {
res.push(cur);
return;
}
// 左括號(hào)還存在，就可以選左括號(hào)
if (left > 0) dfs(cur + '(', left - 1, right);
// 右括號(hào)數(shù)量要大于左括號(hào)，才可以選右括號(hào)
if (right > left) dfs(cur + ')', left, right - 1);
}
dfs('', n, n);
return res;
};
本文參考
「前端該如何準(zhǔn)備數(shù)據(jù)結(jié)構(gòu)和算法？」 「寫給前端的算法進(jìn)階指南，我是如何兩個(gè)月零基礎(chǔ)刷200題」 「(1.8w字)負(fù)重前行，前端工程師如何系統(tǒng)練習(xí)數(shù)據(jù)結(jié)構(gòu)和算法？【上】」
參考鏈接：
結(jié)語(yǔ)
??關(guān)注+點(diǎn)贊+收藏+評(píng)論+轉(zhuǎn)發(fā)??，原創(chuàng)不易，您的支持將會(huì)是我最大的動(dòng)力~
祝愿在準(zhǔn)備春秋招の你，能夠早點(diǎn)結(jié)束，offer 拿到手軟，希望我的文章能夠幫助到你，我們很快會(huì)在下期相遇，給個(gè)贊及時(shí)催更呀~
學(xué)如逆水行舟，不進(jìn)則退
你若喜歡，為小獅子點(diǎn)個(gè)【在看】哦~