寫(xiě)給前端的算法進(jìn)階指南,大佬是如何兩個(gè)月零基礎(chǔ)刷200題

前言

最近國(guó)內(nèi)大廠面試中，出現(xiàn) LeetCode 真題考察的頻率越來(lái)越高了。我也觀察到有越來(lái)越多的前端同學(xué)開(kāi)始關(guān)注算法這個(gè)話題。

但是算法是一個(gè)門(mén)檻很高的東西，在一個(gè)算法新手的眼里，它的智商門(mén)檻要求很高。事實(shí)上是這個(gè)樣子的嗎？如果你懷疑自己的智商不夠去學(xué)習(xí)算法，那么你一定要先看完這篇文章：《天生不聰明》，也正是這篇文章激勵(lì)了我開(kāi)始了算法之路。

這篇文章，我會(huì)先總結(jié)幾個(gè)必學(xué)的題目分類(lèi)，給出這個(gè)分類(lèi)下必做例題的詳細(xì)題解，并且在文章的末尾給出每個(gè)分類(lèi)下必刷的題目的獲取方式。

一定要耐心看到底，會(huì)有重磅干貨。

心路

我從 5 月份準(zhǔn)備離職的時(shí)候開(kāi)始學(xué)習(xí)算法，在此之前對(duì)于算法我是零基礎(chǔ)，在最開(kāi)始我對(duì)于算法的感受也和大家一樣，覺(jué)得自己智商可能不夠，望而卻步。但是看了一些大佬對(duì)于算法和智商之間的關(guān)系，我發(fā)現(xiàn)算法好像也是一個(gè)通過(guò)練習(xí)可以慢慢成長(zhǎng)的學(xué)科，而不是只有智商達(dá)到了某個(gè)點(diǎn)才能有入場(chǎng)券，所以我開(kāi)始了我的算法之路。通過(guò)視頻課程 + 分類(lèi)刷題 + 總結(jié)題解 + 回頭復(fù)習(xí)的方式，我在兩個(gè)月的時(shí)間里把力扣的解題數(shù)量刷到了200題。對(duì)于一個(gè)算法新人來(lái)說(shuō)，這應(yīng)該算是一個(gè)還可以的成績(jī)，這篇文章，我把我總結(jié)的一些學(xué)習(xí)心得，和一些經(jīng)典例題分享給大家。

學(xué)習(xí)方式

1. 分類(lèi)刷題：很多第一次接觸力扣的同學(xué)對(duì)于刷題的方法不太了解，有的人跟著題號(hào)刷，有的人跟著每日一題刷，但是這種漫無(wú)目的的刷題方式一般都會(huì)在中途某一天放棄，或者刷了很久但是卻發(fā)現(xiàn)沒(méi)什么沉淀。這里不啰嗦，直接點(diǎn)明一個(gè)所有大佬都推薦的刷題方法：把自己的學(xué)習(xí)階段分散成幾個(gè)時(shí)間段去刷不同分類(lèi)的題型，比如第一周專(zhuān)門(mén)解鏈表相關(guān)題型，第二周專(zhuān)門(mén)解二叉樹(shù)相關(guān)題型。這樣你的知識(shí)會(huì)形成一個(gè)體系，通過(guò)一段時(shí)間的刻意練習(xí)把這個(gè)題型相關(guān)的知識(shí)點(diǎn)強(qiáng)化到你的腦海中，不容易遺忘。

2. 適當(dāng)放棄：很多同學(xué)遇到一個(gè)難題，非得埋頭鉆研，干他 2 個(gè)小時(shí)。最后挫敗感十足，久而久之可能就放棄了算法之路。要知道算法是個(gè)沉淀了幾十年的領(lǐng)域，題解里的某個(gè)算法可能是某些教授研究很多年的心血，你想靠自己一個(gè)新手去想出來(lái)同等優(yōu)秀的解法，豈不是想太多了。所以要學(xué)會(huì)適當(dāng)放棄，一般來(lái)說(shuō)，比較有目的性（面試）刷題的同學(xué)，他面對(duì)一道新的題目毫無(wú)頭緒的話，會(huì)在 10 分鐘之內(nèi)直接放棄去看題解，然后記錄下來(lái)，反復(fù)復(fù)習(xí)，直到這個(gè)解法成為自己的知識(shí)為止。這是效率最高的學(xué)習(xí)辦法。

3. 接受自己是新手：沒(méi)錯(cuò)，說(shuō)的難聽(tīng)一點(diǎn)，接受自己不是天才這個(gè)現(xiàn)實(shí)。你在刷題的過(guò)程中會(huì)遇到很多困擾你的時(shí)候，比如相同的題型已經(jīng)看過(guò)例題，稍微變了條件就解不出來(lái)。或者對(duì)于一個(gè) easy 難度的題毫無(wú)頭緒。或者甚至看不懂別人的題解（沒(méi)錯(cuò)我經(jīng)常）相信我，這很正常，不能說(shuō)明你不適合學(xué)習(xí)算法，只能說(shuō)明算法確實(shí)是一個(gè)博大精深的領(lǐng)域，把自己在其他領(lǐng)域的沉淀拋開(kāi)來(lái)，接受自己是新手這個(gè)事實(shí)，多看題解，多請(qǐng)教別人。

分類(lèi)大綱

1. 算法的復(fù)雜度分析。
2. 排序算法，以及他們的區(qū)別和優(yōu)化。
3. 數(shù)組中的雙指針、滑動(dòng)窗口思想。
4. 利用 Map 和 Set 處理查找表問(wèn)題。
5. 鏈表的各種問(wèn)題。
6. 利用遞歸和迭代法解決二叉樹(shù)問(wèn)題。
7. 棧、隊(duì)列、DFS、BFS。
8. 回溯法、貪心算法、動(dòng)態(tài)規(guī)劃。

題解

接下來(lái)我會(huì)放出幾個(gè)分類(lèi)的經(jīng)典題型，以及我對(duì)應(yīng)的講解，當(dāng)做開(kāi)胃菜，并且在文章的末尾我會(huì)給出獲取每個(gè)分類(lèi)推薦你去刷的題目的合集，記得看到底哦。

查找表問(wèn)題

兩個(gè)數(shù)組的交集 II-350

給定兩個(gè)數(shù)組，編寫(xiě)一個(gè)函數(shù)來(lái)計(jì)算它們的交集。

示例?1:

輸入:?nums1?=?[1,2,2,1],?nums2?=?[2,2]
輸出:?[2,2]
示例?2:

輸入:?nums1?=?[4,9,5],?nums2?=?[9,4,9,8,4]
輸出:?[4,9]

來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/intersection-of-two-arrays-ii
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

---

為兩個(gè)數(shù)組分別建立 map，用來(lái)存儲(chǔ) num -> count 的鍵值對(duì)，統(tǒng)計(jì)每個(gè)數(shù)字出現(xiàn)的數(shù)量。

然后對(duì)其中一個(gè) map 進(jìn)行遍歷，查看這個(gè)數(shù)字在兩個(gè)數(shù)組中分別出現(xiàn)的數(shù)量，取出現(xiàn)的最小的那個(gè)數(shù)量（比如數(shù)組 1 中出現(xiàn)了 1 次，數(shù)組 2 中出現(xiàn)了 2 次，那么交集應(yīng)該取 1 次），push 到結(jié)果數(shù)組中即可。

/**
?*?@param?{number[]}?nums1
?*?@param?{number[]}?nums2
?*?@return?{number[]}
?*/
let?intersect?=?function?(nums1,?nums2)?{
??let?map1?=?makeCountMap(nums1)
??let?map2?=?makeCountMap(nums2)
??let?res?=?[]
??for?(let?num?of?map1.keys())?{
????const?count1?=?map1.get(num)
????const?count2?=?map2.get(num)

????if?(count2)?{
??????const?pushCount?=?Math.min(count1,?count2)
??????for?(let?i?=?0;?i?????????res.push(num)
??????}
????}
??}
??return?res
}

function?makeCountMap(nums)?{
??let?map?=?new?Map()
??for?(let?i?=?0;?i?????let?num?=?nums[i]
????let?count?=?map.get(num)
????if?(count)?{
??????map.set(num,?count?+?1)
????}?else?{
??????map.set(num,?1)
????}
??}
??return?map
}

雙指針問(wèn)題

最接近的三數(shù)之和-16

給定一個(gè)包括 ?n 個(gè)整數(shù)的數(shù)組 ?nums ?和 一個(gè)目標(biāo)值 ?target。找出 ?nums ?中的三個(gè)整數(shù)，使得它們的和與 ?target ?最接近。返回這三個(gè)數(shù)的和。假定每組輸入只存在唯一答案。

示例：

輸入：nums =?[-1,2,1,-4], target = 1
輸出：2
解釋?zhuān)号c target 最接近的和是 2 (-1 + 2 + 1 = 2)?。

提示：

3 <= nums.length <= 10^3-10^3 <= nums[i] <= 10^3-10^4 <= target <= 10^4

來(lái)源：力扣（LeetCode）

鏈接：https://leetcode-cn.com/problems/3sum-closest

著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

---

先按照升序排序，然后分別從左往右依次選擇一個(gè)基礎(chǔ)點(diǎn) i（0 <= i <= nums.length - 3），在基礎(chǔ)點(diǎn)的右側(cè)用雙指針去不斷的找最小的差值。

假設(shè)基礎(chǔ)點(diǎn)是 i，初始化的時(shí)候，雙指針?lè)謩e是：

• left：i + 1，基礎(chǔ)點(diǎn)右邊一位。
• right: nums.length - 1 數(shù)組最后一位。

然后求此時(shí)的和，如果和大于 target，那么可以把右指針左移一位，去試試更小一點(diǎn)的值，反之則把左指針右移。

在這個(gè)過(guò)程中，不斷更新全局的最小差值 min，和此時(shí)記錄下來(lái)的和 res。

最后返回 res 即可。

/**
?*?@param?{number[]}?nums
?*?@param?{number}?target
?*?@return?{number}
?*/
let?threeSumClosest?=?function?(nums,?target)?{
??let?n?=?nums.length
??if?(n?===?3)?{
????return?getSum(nums)
??}
??//?先升序排序?此為解題的前置條件
??nums.sort((a,?b)?=>?a?-?b)

??let?min?=?Infinity?//?和?target?的最小差
??let?res

??//?從左往右依次嘗試定一個(gè)基礎(chǔ)指針?右邊至少再保留兩位?否則無(wú)法湊成3個(gè)
??for?(let?i?=?0;?i?<=?nums.length?-?3;?i++)?{
????let?basic?=?nums[i]
????let?left?=?i?+?1?//?左指針先從?i?右側(cè)的第一位開(kāi)始嘗試
????let?right?=?n?-?1?//?右指針先從數(shù)組最后一項(xiàng)開(kāi)始嘗試

????while?(left???????let?sum?=?basic?+?nums[left]?+?nums[right]?//?三數(shù)求和
??????//?更新最小差
??????let?diff?=?Math.abs(sum?-?target)
??????if?(diff?????????min?=?diff
????????res?=?sum
??????}
??????if?(sum?????????//?求出的和如果小于目標(biāo)值的話?可以嘗試把左指針右移?擴(kuò)大值
????????left++
??????}?else?if?(sum?>?target)?{
????????//?反之則右指針左移
????????right--
??????}?else?{
????????//?相等的話?差就為0?一定是答案
????????return?sum
??????}
????}
??}

??return?res
}

function?getSum(nums)?{
??return?nums.reduce((total,?cur)?=>?total?+?cur,?0)
}

滑動(dòng)窗口問(wèn)題

無(wú)重復(fù)字符的最長(zhǎng)子串-3

給定一個(gè)字符串，請(qǐng)你找出其中不含有重復(fù)字符的 ? 最長(zhǎng)子串 ? 的長(zhǎng)度。

示例 ?1:

輸入:?"abcabcbb"
輸出:?3
解釋:?因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是?"abc"，所以其長(zhǎng)度為 3。

示例 2:

輸入:?"bbbbb"
輸出:?1
解釋:?因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是?"b"，所以其長(zhǎng)度為 1。

示例 3:

輸入:?"pwwkew"
輸出:?3
解釋:?因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是?"wke"，所以其長(zhǎng)度為 3。
?????請(qǐng)注意，你的答案必須是?子串?的長(zhǎng)度，"pwke"?是一個(gè)子序列，不是子串。

來(lái)源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters 著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

---

這題是比較典型的滑動(dòng)窗口問(wèn)題，定義一個(gè)左邊界 left 和一個(gè)右邊界 right，形成一個(gè)窗口，并且在這個(gè)窗口中保證不出現(xiàn)重復(fù)的字符串。

這需要用到一個(gè)新的變量 freqMap，用來(lái)記錄窗口中的字母出現(xiàn)的頻率數(shù)。在此基礎(chǔ)上，先嘗試取窗口的右邊界再右邊一個(gè)位置的值，也就是 str[right + 1]，然后拿這個(gè)值去 freqMap 中查找：

1. 這個(gè)值沒(méi)有出現(xiàn)過(guò)，那就直接把 right ++，擴(kuò)大窗口右邊界。
2. 如果這個(gè)值出現(xiàn)過(guò)，那么把 left ++，縮進(jìn)左邊界，并且記得把 str[left] 位置的值在 freqMap 中減掉。

循環(huán)條件是 left < str.length，允許左邊界一直滑動(dòng)到字符串的右界。

/**
?*?@param?{string}?s
?*?@return?{number}
?*/
let?lengthOfLongestSubstring?=?function?(str)?{
??let?n?=?str.length
??//?滑動(dòng)窗口為s[left...right]
??let?left?=?0
??let?right?=?-1
??let?freqMap?=?{}?//?記錄當(dāng)前子串中下標(biāo)對(duì)應(yīng)的出現(xiàn)頻率
??let?max?=?0?//?找到的滿足條件子串的最長(zhǎng)長(zhǎng)度

??while?(left?????let?nextLetter?=?str[right?+?1]
????if?(!freqMap[nextLetter]?&&?nextLetter?!==?undefined)?{
??????freqMap[nextLetter]?=?1
??????right++
????}?else?{
??????freqMap[str[left]]?=?0
??????left++
????}
????max?=?Math.max(max,?right?-?left?+?1)
??}

??return?max
}

鏈表問(wèn)題

兩兩交換鏈表中的節(jié)點(diǎn)-24

給定一個(gè)鏈表，兩兩交換其中相鄰的節(jié)點(diǎn)，并返回交換后的鏈表。

你不能只是單純的改變節(jié)點(diǎn)內(nèi)部的值，而是需要實(shí)際的進(jìn)行節(jié)點(diǎn)交換。

示例:

給定?1->2->3->4,?你應(yīng)該返回?2->1->4->3.

來(lái)源：力扣（LeetCode）

鏈接：https://leetcode-cn.com/problems/swap-nodes-in-pairs

著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

---

這題本意比較簡(jiǎn)單，1 -> 2 -> 3 -> 4 的情況下可以定義一個(gè)遞歸的輔助函數(shù) helper，這個(gè)輔助函數(shù)對(duì)于節(jié)點(diǎn)和它的下一個(gè)節(jié)點(diǎn)進(jìn)行交換，比如 helper(1) 處理 1 -> 2，并且把交換變成 2 -> 1 的尾節(jié)點(diǎn) 1的next繼續(xù)指向 helper(3)也就是交換后的 4 -> 3。

邊界情況在于，如果順利的作了兩兩交換，那么交換后我們的函數(shù)返回出去的是 交換后的頭部節(jié)點(diǎn)，但是如果是奇數(shù)剩余項(xiàng)的情況下，沒(méi)辦法做交換，那就需要直接返回 原本的頭部節(jié)點(diǎn)。這個(gè)在 helper函數(shù)和主函數(shù)中都有體現(xiàn)。

let?swapPairs?=?function?(head)?{
??if?(!head)?return?null
??let?helper?=?function?(node)?{
????let?tempNext?=?node.next
????if?(tempNext)?{
??????let?tempNextNext?=?node.next.next
??????node.next.next?=?node
??????if?(tempNextNext)?{
????????node.next?=?helper(tempNextNext)
??????}?else?{
????????node.next?=?null
??????}
????}
????return?tempNext?||?node
??}

??let?res?=?helper(head)

??return?res?||?head
}

深度優(yōu)先遍歷問(wèn)題

二叉樹(shù)的所有路徑-257

給定一個(gè)二叉樹(shù)，返回所有從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑。

說(shuō)明:? 葉子節(jié)點(diǎn)是指沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)。

示例:

輸入:

???1
?/???\
2?????3
?\
??5

輸出:?["1->2->5",?"1->3"]

解釋:?所有根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑為:?1->2->5,?1->3

來(lái)源：力扣（LeetCode）

鏈接：https://leetcode-cn.com/problems/binary-tree-paths

著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

---

用當(dāng)前節(jié)點(diǎn)的值去拼接左右子樹(shù)遞歸調(diào)用當(dāng)前函數(shù)獲得的所有路徑。

也就是根節(jié)點(diǎn)拼上以左子樹(shù)為根節(jié)點(diǎn)得到的路徑，加上根節(jié)點(diǎn)拼上以右子樹(shù)為根節(jié)點(diǎn)得到的所有路徑。

直到葉子節(jié)點(diǎn)，僅僅返回包含當(dāng)前節(jié)點(diǎn)的值的數(shù)組。

let?binaryTreePaths?=?function?(root)?{
??let?res?=?[]
??if?(!root)?{
????return?res
??}

??if?(!root.left?&&?!root.right)?{
????return?[`${root.val}`]
??}

??let?leftPaths?=?binaryTreePaths(root.left)
??let?rightPaths?=?binaryTreePaths(root.right)

??leftPaths.forEach((leftPath)?=>?{
????res.push(`${root.val}->${leftPath}`)
??})
??rightPaths.forEach((rightPath)?=>?{
????res.push(`${root.val}->${rightPath}`)
??})

??return?res
}

廣度優(yōu)先遍歷（BFS）問(wèn)題

在每個(gè)樹(shù)行中找最大值-515

https://leetcode-cn.com/problems/find-largest-value-in-each-tree-row

您需要在二叉樹(shù)的每一行中找到最大的值。

輸入:

??????????1
?????????/?\
????????3???2
???????/?\???\
??????5???3???9

輸出:?[1,?3,?9]

---

這是一道典型的 BFS 題目，BFS 的套路其實(shí)就是維護(hù)一個(gè) queue 隊(duì)列，在讀取子節(jié)點(diǎn)的時(shí)候同時(shí)把發(fā)現(xiàn)的孫子節(jié)點(diǎn) push 到隊(duì)列中，但是先不處理，等到這一輪隊(duì)列中的子節(jié)點(diǎn)處理完成以后，下一輪再繼續(xù)處理的就是孫子節(jié)點(diǎn)了，這就實(shí)現(xiàn)了層序遍歷，也就是一層層的去處理。

但是這里有一個(gè)問(wèn)題卡住我了一會(huì)，就是如何知道當(dāng)前處理的節(jié)點(diǎn)是哪個(gè)層級(jí)的，在最開(kāi)始的時(shí)候我嘗試寫(xiě)了一下二叉樹(shù)求某個(gè) index 所在層級(jí)的公式，但是發(fā)現(xiàn)這種公式只能處理「平衡二叉樹(shù)」。

后面看題解發(fā)現(xiàn)他們都沒(méi)有專(zhuān)門(mén)維護(hù)層級(jí)，再仔細(xì)一看才明白層級(jí)的思路：

其實(shí)就是在每一輪 while 循環(huán)里，再開(kāi)一個(gè) for 循環(huán)，這個(gè) for 循環(huán)的終點(diǎn)是「提前緩存好的 length 快照」，也就是進(jìn)入這輪 while 循環(huán)時(shí)，queue 的長(zhǎng)度。其實(shí)這個(gè)長(zhǎng)度就恰好代表了「一個(gè)層級(jí)的長(zhǎng)度」。

緩存后，for 循環(huán)里可以安全的把子節(jié)點(diǎn) push 到數(shù)組里而不影響緩存的當(dāng)前層級(jí)長(zhǎng)度。

另外有一個(gè)小 tips，在 for 循環(huán)處理完成后，應(yīng)該要把 queue 的長(zhǎng)度截取掉上述的緩存長(zhǎng)度。一開(kāi)始我使用的是 queue.splice(0, len)，結(jié)果速度只擊敗了 33%的人。后面換成 for 循環(huán)中去一個(gè)一個(gè)shift來(lái)截取，速度就擊敗了 77%的人。

/**
?*?@param?{TreeNode}?root
?*?@return?{number[]}
?*/
let?largestValues?=?function?(root)?{
??if?(!root)?return?[]
??let?queue?=?[root]
??let?maximums?=?[]

??while?(queue.length)?{
????let?max?=?Number.MIN_SAFE_INTEGER
????//?這里需要先緩存length?這個(gè)length代表當(dāng)前層級(jí)的所有節(jié)點(diǎn)
????//?在循環(huán)開(kāi)始后?會(huì)push新的節(jié)點(diǎn)?length就不穩(wěn)定了
????let?len?=?queue.length
????for?(let?i?=?0;?i???????let?node?=?queue[i]
??????max?=?Math.max(node.val,?max)

??????if?(node.left)?{
????????queue.push(node.left)
??????}
??????if?(node.right)?{
????????queue.push(node.right)
??????}
????}

????//?本「層級(jí)」處理完畢，截取掉。
????for?(let?i?=?0;?i???????queue.shift()
????}

????//?這個(gè)for循環(huán)結(jié)束后?代表當(dāng)前層級(jí)的節(jié)點(diǎn)全部處理完畢
????//?直接把計(jì)算出來(lái)的最大值push到數(shù)組里即可。
????maximums.push(max)
??}

??return?maximums
}

棧問(wèn)題

有效的括號(hào)-20

給定一個(gè)只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判斷字符串是否有效。

有效字符串需滿足：

• 左括號(hào)必須用相同類(lèi)型的右括號(hào)閉合。
• 左括號(hào)必須以正確的順序閉合。
• 注意空字符串可被認(rèn)為是有效字符串。

示例 1:

輸入:?"()"
輸出:?true

示例 2:

輸入:?"()[]{}"
輸出:?true

示例 3:

輸入:?"(]"
輸出:?false

示例 4:

輸入:?"([)]"
輸出:?false

示例 5:

輸入:?"{[]}"
輸出:?true

https://leetcode-cn.com/problems/valid-parentheses

---

提前記錄好左括號(hào)類(lèi)型 (, {, [和右括號(hào)類(lèi)型), }, ]的映射表，當(dāng)遍歷中遇到左括號(hào)的時(shí)候，就放入棧 stack 中（其實(shí)就是數(shù)組），當(dāng)遇到右括號(hào)時(shí)，就把 stack 頂?shù)脑?pop 出來(lái)，看一下是否是這個(gè)右括號(hào)所匹配的左括號(hào)（比如 ( 和 ) 是一對(duì)匹配的括號(hào)）。

當(dāng)遍歷結(jié)束后，棧中不應(yīng)該剩下任何元素，返回成功，否則就是失敗。

/**
?*?@param?{string}?s
?*?@return?{boolean}
?*/
let?isValid?=?function?(s)?{
??let?sl?=?s.length
??if?(sl?%?2?!==?0)?return?false
??let?leftToRight?=?{
????"{":?"}",
????"[":?"]",
????"(":?")",
??}
??//?建立一個(gè)反向的?value?->?key?映射表
??let?rightToLeft?=?createReversedMap(leftToRight)
??//?用來(lái)匹配左右括號(hào)的棧
??let?stack?=?[]

??for?(let?i?=?0;?i?????let?bracket?=?s[i]
????//?左括號(hào)?放進(jìn)棧中
????if?(leftToRight[bracket])?{
??????stack.push(bracket)
????}?else?{
??????let?needLeftBracket?=?rightToLeft[bracket]
??????//?左右括號(hào)都不是?直接失敗
??????if?(!needLeftBracket)?{
????????return?false
??????}

??????//?棧中取出最后一個(gè)括號(hào)?如果不是需要的那個(gè)左括號(hào)?就失敗
??????let?lastBracket?=?stack.pop()
??????if?(needLeftBracket?!==?lastBracket)?{
????????return?false
??????}
????}
??}

??if?(stack.length)?{
????return?false
??}
??return?true
}

function?createReversedMap(map)?{
??return?Object.keys(map).reduce((prev,?key)?=>?{
????const?value?=?map[key]
????prev[value]?=?key
????return?prev
??},?{})
}

遞歸與回溯

直接看我寫(xiě)的這兩篇文章即可，遞歸與回溯甚至是平常業(yè)務(wù)開(kāi)發(fā)中最常見(jiàn)的算法場(chǎng)景之一了，所以我重點(diǎn)總結(jié)了兩篇文章。

《前端電商 sku 的全排列算法很難嗎？學(xué)會(huì)這個(gè)套路，徹底掌握排列組合。》[1]

前端「N 皇后」遞歸回溯經(jīng)典問(wèn)題圖解[2]

動(dòng)態(tài)規(guī)劃

打家劫舍 - 198

你是一個(gè)專(zhuān)業(yè)的小偷，計(jì)劃偷竊沿街的房屋。每間房?jī)?nèi)都藏有一定的現(xiàn)金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統(tǒng)，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統(tǒng)會(huì)自動(dòng)報(bào)警。

給定一個(gè)代表每個(gè)房屋存放金額的非負(fù)整數(shù)數(shù)組，計(jì)算你在不觸動(dòng)警報(bào)裝置的情況下，能夠偷竊到的最高金額。

示例?1:

輸入:?[1,2,3,1]
輸出:?4
解釋:?偷竊 1 號(hào)房屋?(金額?= 1)?，然后偷竊 3 號(hào)房屋?(金額?= 3)。
??偷竊到的最高金額?= 1 + 3 = 4 。
示例?2:

輸入:?[2,7,9,3,1]
輸出:?12
解釋:?偷竊 1 號(hào)房屋?(金額?= 2), 偷竊 3 號(hào)房屋?(金額?= 9)，接著偷竊 5 號(hào)房屋?(金額?= 1)。
??偷竊到的最高金額?= 2 + 9 + 1 = 12 。

來(lái)源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/house-robber 著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

---

動(dòng)態(tài)規(guī)劃的一個(gè)很重要的過(guò)程就是找到「狀態(tài)」和「狀態(tài)轉(zhuǎn)移方程」，在這個(gè)問(wèn)題里，設(shè) i 是當(dāng)前屋子的下標(biāo)，狀態(tài)就是 以 i 為起點(diǎn)偷竊的最大價(jià)值

在某一個(gè)房子面前，盜賊只有兩種選擇：偷或者不偷。

1. 偷的話，價(jià)值就是「當(dāng)前房子的價(jià)值」+「下兩個(gè)房子開(kāi)始盜竊的最大價(jià)值」
2. 不偷的話，價(jià)值就是「下一個(gè)房子開(kāi)始盜竊的最大價(jià)值」

在這兩個(gè)值中，選擇最大值記錄在 dp[i]中，就得到了以 i 為起點(diǎn)所能偷竊的最大價(jià)值。。

動(dòng)態(tài)規(guī)劃的起手式，找基礎(chǔ)狀態(tài)，在這題中，以終點(diǎn)為起點(diǎn)的最大價(jià)值一定是最好找的，因?yàn)榻K點(diǎn)不可能再繼續(xù)往后偷竊了，所以設(shè) n 為房子的總數(shù)量， dp[n - 1] 就是 nums[n - 1]，小偷只能選擇偷竊這個(gè)房子，而不能跳過(guò)去選擇下一個(gè)不存在的房子。

那么就找到了動(dòng)態(tài)規(guī)劃的狀態(tài)轉(zhuǎn)移方程：

//?搶劫當(dāng)前房子
robNow?=?nums[i]?+?dp[i?+?2]?//?「當(dāng)前房子的價(jià)值」?+?「i?+?2?下標(biāo)房子為起點(diǎn)的最大價(jià)值」

//?不搶當(dāng)前房子，搶下一個(gè)房子
robNext?=?dp[i?+?1]?//「i?+?1?下標(biāo)房子為起點(diǎn)的最大價(jià)值」

//?兩者選擇最大值
dp[i]?=?Math.max(robNow,?robNext)

，并且從后往前求解。

function?(nums)?{
??if?(!nums.length)?{
????return?0;
??}
??let?dp?=?[];

??for?(let?i?=?nums.length?-?1;?i?>=?0;?i--)?{
????let?robNow?=?nums[i]?+?(dp[i?+?2]?||?0)
????let?robNext?=?dp[i?+?1]?||?0

????dp[i]?=?Math.max(robNow,?robNext)
??}

??return?dp[0];
};

最后返回 以 0 為起點(diǎn)開(kāi)始打劫的最大價(jià)值 即可。

貪心算法問(wèn)題

分發(fā)餅干-455

假設(shè)你是一位很棒的家長(zhǎng)，想要給你的孩子們一些小餅干。但是，每個(gè)孩子最多只能給一塊餅干。對(duì)每個(gè)孩子 i ，都有一個(gè)胃口值 ?gi ，這是能讓孩子們滿足胃口的餅干的最小尺寸；并且每塊餅干 j ，都有一個(gè)尺寸 sj 。如果 sj >= gi ，我們可以將這個(gè)餅干 j 分配給孩子 i ，這個(gè)孩子會(huì)得到滿足。你的目標(biāo)是盡可能滿足越多數(shù)量的孩子，并輸出這個(gè)最大數(shù)值。

注意：

你可以假設(shè)胃口值為正。一個(gè)小朋友最多只能擁有一塊餅干。

示例?1:

輸入:?[1,2,3],?[1,1]

輸出:?1

解釋:
你有三個(gè)孩子和兩塊小餅干，3個(gè)孩子的胃口值分別是：1,2,3。
雖然你有兩塊小餅干，由于他們的尺寸都是1，你只能讓胃口值是1的孩子滿足。
所以你應(yīng)該輸出1。
示例?2:

輸入:?[1,2],?[1,2,3]

輸出:?2

解釋:
你有兩個(gè)孩子和三塊小餅干，2個(gè)孩子的胃口值分別是1,2。
你擁有的餅干數(shù)量和尺寸都足以讓所有孩子滿足。
所以你應(yīng)該輸出2.

來(lái)源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/assign-cookies 著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

---

把餅干和孩子的需求都排序好，然后從最小的餅干分配給需求最小的孩子開(kāi)始，不斷的嘗試新的餅干和新的孩子，這樣能保證每個(gè)分給孩子的餅干都恰到好處的不浪費(fèi)，又滿足需求。

利用雙指針不斷的更新 i 孩子的需求下標(biāo)和 j餅干的值，直到兩者有其一達(dá)到了終點(diǎn)位置：

1. 如果當(dāng)前的餅干不滿足孩子的胃口，那么把 j++ 尋找下一個(gè)餅干，不用擔(dān)心這個(gè)餅干被浪費(fèi)，因?yàn)檫@個(gè)餅干更不可能滿足下一個(gè)孩子（胃口更大）。
2. 如果滿足，那么 i++; j++; count++ 記錄當(dāng)前的成功數(shù)量，繼續(xù)尋找下一個(gè)孩子和下一個(gè)餅干。

/**
?*?@param?{number[]}?g
?*?@param?{number[]}?s
?*?@return?{number}
?*/
let?findContentChildren?=?function?(g,?s)?{
??g.sort((a,?b)?=>?a?-?b)
??s.sort((a,?b)?=>?a?-?b)

??let?i?=?0
??let?j?=?0

??let?count?=?0
??while?(j?????let?need?=?g[i]
????let?cookie?=?s[j]

????if?(cookie?>=?need)?{
??????count++
??????i++
??????j++
????}?else?{
??????j++
????}
??}

??return?count
}

必做題目

其實(shí)寫(xiě)了這么多，以上分類(lèi)所提到的題目，只是當(dāng)前分類(lèi)下比較適合作為例題來(lái)講解的題目而已，在整個(gè) LeetCode 學(xué)習(xí)過(guò)程中只是冰山一角。這些題可以作為你深入這個(gè)分類(lèi)的一個(gè)入門(mén)例題，但是不可避免的是，你必須去下苦功夫刷每個(gè)分類(lèi)下的其他經(jīng)典題目。

如果你信任我，你也可以在我維護(hù)的題解倉(cāng)庫(kù)的 Issues 中[3]獲取各個(gè)分類(lèi)下必做題目的詳細(xì)題解（拿到了記得收藏），我跟著一個(gè)ACM 亞洲區(qū)獎(jiǎng)牌獲得者給出的提綱，整理了100+道必做題目的詳細(xì)題解。

那么什么叫必做題目呢？

1. 它核心考察算法思想，而不是奇巧淫技。
2. 它考察的知識(shí)點(diǎn)，可以舉一反三的應(yīng)用到很多相似題目上。
3. 面試熱門(mén)題，大廠喜歡考這個(gè)題目，說(shuō)明這個(gè)知識(shí)點(diǎn)很重要。

當(dāng)然你也可以去知乎等平臺(tái)搜索相關(guān)的問(wèn)題，也會(huì)有很多人總結(jié)，但是比我總結(jié)的全的不多見(jiàn)。100 多題說(shuō)多也不多，說(shuō)少也不少。認(rèn)真學(xué)習(xí)、解答、吸收這些題目大概要花費(fèi)1 個(gè)月左右的時(shí)間。但是相信我，1 個(gè)月以后你在算法方面會(huì)脫胎換骨，應(yīng)對(duì)國(guó)內(nèi)大廠的算法面試也會(huì)變得游刃有余。

總結(jié)

關(guān)于算法在工程方面有用與否的爭(zhēng)論，已經(jīng)是一個(gè)經(jīng)久不衰的話題了。這里不討論這個(gè)，我個(gè)人的觀念是絕對(duì)有用的，只要你不是一個(gè)甘于只做簡(jiǎn)單需求的人，你一定會(huì)在后續(xù)開(kāi)發(fā)架構(gòu)、遇到難題的過(guò)程中或多或少的從你的算法學(xué)習(xí)中受益。

再說(shuō)的功利點(diǎn)，就算是為了面試，刷算法能夠進(jìn)入大廠也是你職業(yè)生涯的一個(gè)起飛點(diǎn)，大廠給你帶來(lái)的的環(huán)境、嚴(yán)格的 Code Review、完善的導(dǎo)師機(jī)制和協(xié)作流程也是你作為工程師所夢(mèng)寐以求的。

希望這篇文章能讓你不再繼續(xù)害怕算法面試，跟著我一起攻下這座城堡吧，大家加油！

參考資料[1]

《前端電商 sku 的全排列算法很難嗎？學(xué)會(huì)這個(gè)套路，徹底掌握排列組合。》: https://juejin.im/post/5ee6d9026fb9a047e60815f1

[2]

前端「N 皇后」遞歸回溯經(jīng)典問(wèn)題圖解: https://juejin.im/post/5eeafa406fb9a058b51e60c0

[3]

我維護(hù)的題解倉(cāng)庫(kù)的 Issues 中: https://github.com/sl1673495/leetcode-javascript/issues

推薦閱讀

我的公眾號(hào)能帶來(lái)什么價(jià)值？(文末有送書(shū)規(guī)則，一定要看)

每個(gè)前端工程師都應(yīng)該了解的圖片知識(shí)(長(zhǎng)文建議收藏)

為什么現(xiàn)在面試總是面試造火箭？