[[325909]]

 

對于許多開發(fā)人員而言，編寫采訪編碼的過程會引起焦慮。 涉及的內(nèi)容太多，常常感覺很多與開發(fā)人員在日常工作中所做的事情無關(guān)，這只會增加壓力。

結(jié)果之一是，開發(fā)人員現(xiàn)在通常花數(shù)周的時間在LeetCode等網(wǎng)站上瀏覽數(shù)百個面試問題。 在面試之前，我談到的焦慮癥開發(fā)人員最常見的觀點之一是：我是否解決了足夠的練習(xí)題? 我還能做更多嗎?

這就是為什么我嘗試著重于幫助開發(fā)人員掌握每個問題背后的基本模式的原因，因此他們不必擔(dān)心解決數(shù)百個問題而遭受Leetcode疲勞的困擾。 如果您了解通用模式，則可以將它們用作模板來解決無數(shù)微小變化的其他許多問題。

在這里，我列出了可用于解決任何編碼面試問題的前14種模式，以及如何識別每種模式以及每種模式的一些示例性問題。 這只是表面上的問題-我強烈建議您查看Grokking the Coding Interview：編碼問題的模式以獲取全面的解釋，示例和編碼實踐。

以下模式假定您已經(jīng)精通數(shù)據(jù)結(jié)構(gòu)。 如果還沒有的話，請查看這些有關(guān)數(shù)據(jù)結(jié)構(gòu)的復(fù)習(xí)課程。

這是我們今天要看的14種模式。

• 滑動窗口
• 2個指針或迭代器
• 快指針或慢指針或迭代器
• 合并間隔
• 循環(huán)排序
• 就地反轉(zhuǎn)鏈表
• 樹BFS
• 樹DFS
• 兩堆
• 子集
• 修改后的二進制搜索
• 前K個元素
• K路合并
• 拓撲排序

讓我們開始吧!

1.推拉窗

滑動窗口模式用于對給定數(shù)組或鏈接列表的特定窗口大小執(zhí)行所需的操作，例如查找包含全1的最長子數(shù)組。 滑動窗口從第一個元素開始，一直向右移動一個元素，并根據(jù)要解決的問題調(diào)整窗口的長度。 在某些情況下，窗口大小保持不變，而在其他情況下，窗口大小會增大或縮小。

 

 

以下是一些可以確定給定問題可能需要滑動窗口的方式：

• 問題輸入是線性數(shù)據(jù)結(jié)構(gòu)，例如鏈表，數(shù)組或字符串
• 要求您找到最長/最短的子字符串，子數(shù)組或所需的值

您將滑動窗口模式用于以下常見問題：

• 大小為" K"的最大總和子數(shù)組(簡單)
• 帶有" K"個不同字符的最長子字符串(中)
• 字謎(硬)

2.兩個指針或迭代器

"兩個指針"是一種模式，其中兩個指針串聯(lián)遍歷數(shù)據(jù)結(jié)構(gòu)，直到其中一個或兩個指針都達到特定條件為止。 在排序數(shù)組或鏈表中搜索對時，兩個指針通常很有用; 例如，當(dāng)您必須將數(shù)組的每個元素與其他元素進行比較時。

需要兩個指針，因為僅使用指針，您將不得不不斷地循環(huán)遍歷數(shù)組以找到答案。 用單個迭代器來回進行此操作對于時間和空間復(fù)雜度而言效率低下-一種稱為漸近分析的概念。 盡管使用1個指針的強力或樸素的解決方案將起作用，但它會產(chǎn)生類似于O(n²)的線。 在許多情況下，兩個指針可以幫助您找到具有更好空間或運行時復(fù)雜性的解決方案。

 

 

確定何時使用"兩指針"方法的方法：

• 在處理排序數(shù)組(或鏈接列表)并且需要找到一組滿足某些約束的元素時，它將遇到一些問題。
• 數(shù)組中的元素集是一對，三元組甚至是子數(shù)組

以下是具有兩個指針模式的一些問題：

• 平方排序數(shù)組(簡單)
• 總計為零的三元組(中)
• 比較包含退格鍵的字符串(中)

3.快速和慢速指針

快速和慢速指針方法，也稱為Hare&Tortoise算法，是一種指針算法，它使用兩個指針以不同的速度在數(shù)組(或序列/鏈表)中移動。 處理循環(huán)鏈表或數(shù)組時，此方法非常有用。

通過以不同的速度移動(例如，在循環(huán)鏈表中)，該算法證明兩個指針必然會合。 一旦兩個指針都處于循環(huán)循環(huán)中，快速指針應(yīng)捕獲慢速指針。

 

 

您如何確定何時使用快速和慢速模式?

• 該問題將處理鏈表或數(shù)組中的循環(huán)
• 當(dāng)您需要知道某個元素的位置或鏈表的總長度時。

什么時候應(yīng)該在上面提到的"兩指針"方法上使用它?

• 在某些情況下，您不應(yīng)該使用"兩指針"方法，例如在單鏈列表中，您不能向后移動。 何時使用快速和慢速模式的一個例子是，當(dāng)您嘗試確定鏈接列表是否是回文。

具有快速和慢速指針模式的問題：

• 鏈接列表周期(簡單)
• 回文鏈接列表(中)
• 循環(huán)循環(huán)陣列(硬)

4.合并間隔

合并間隔模式是處理重疊間隔的有效技術(shù)。 在很多涉及間隔的問題中，您需要找到重疊的間隔，或者如果它們重疊，則需要合并間隔。 該模式如下所示：

給定兩個間隔(" a"和" b")，這兩個間隔可以通過六種不同的方式相互關(guān)聯(lián)：

 

 

了解和認識這六個情況將幫助您解決從插入間隔到優(yōu)化間隔合并的各種問題。

您如何確定何時使用"合并間隔"模式?

• 如果要求您僅以互斥間隔生成列表
• 如果您聽到術(shù)語"重疊間隔"。

合并間隔問題模式：

• 區(qū)間相交(中)
• 最大CPU負載(硬)

5.循環(huán)排序

此模式描述了一種有趣的方法來處理涉及包含給定范圍內(nèi)的數(shù)字的數(shù)組的問題。 循環(huán)排序模式一次在數(shù)組上迭代一個數(shù)字，如果要迭代的當(dāng)前數(shù)字不在正確的索引處，則將其與在其正確的索引處的數(shù)字交換。 您可以嘗試將數(shù)字放置在正確的索引中，但這會導(dǎo)致O(n ^ 2)的復(fù)雜度不是最佳的，因此是循環(huán)排序模式。

 

 

如何識別這種模式?

• 它們將是涉及編號在給定范圍內(nèi)的排序數(shù)組的問題
• 如果問題要求您在排序/旋轉(zhuǎn)數(shù)組中查找缺失/重復(fù)/最小的數(shù)字

具有循環(huán)排序模式的問題：

• 查找丟失的號碼(簡單)
• 查找最小的遺漏正數(shù)(中)

6.就地反轉(zhuǎn)鏈表

在很多問題中，可能會要求您反向鏈接列表的一組節(jié)點之間的鏈接。 通常，約束是您需要就地執(zhí)行此操作，即使用現(xiàn)有的節(jié)點對象并且不使用額外的內(nèi)存。 這是上面提到的模式有用的地方。

此模式一次反轉(zhuǎn)一個節(jié)點，其中一個變量(當(dāng)前)指向鏈接列表的開頭，而一個變量(上一個)將指向您已處理的上一個節(jié)點。 以鎖定步驟的方式，您可以通過將當(dāng)前節(jié)點指向上一個節(jié)點來反轉(zhuǎn)該節(jié)點，然后再移動到下一個節(jié)點。 另外，您將更新變量" previous"以始終指向您已處理的上一個節(jié)點。

 

 

如何確定何時使用此模式：

• 如果要求您在不占用額外內(nèi)存的情況下反向鏈接列表

鏈表模式就地反轉(zhuǎn)的問題：

• 撤消子列表(中)
• 反轉(zhuǎn)每個K元素子列表(中)

7.樹BFS

該模式基于廣度優(yōu)先搜索(BFS)技術(shù)來遍歷樹，并使用隊列來跟蹤某個級別的所有節(jié)點，然后再跳轉(zhuǎn)到下一個級別。 使用這種方法可以有效地解決涉及逐級遍歷樹的任何問題。

Tree BFS模式的工作原理是將根節(jié)點推送到隊列，然后不斷迭代直到隊列為空。 對于每次迭代，我們都刪除隊列開頭的節(jié)點，然后"訪問"該節(jié)點。 從隊列中刪除每個節(jié)點后，我們還將其所有子節(jié)點插入隊列。

如何識別Tree BFS模式：

• 如果要求您逐級遍歷一棵樹(或逐級遍歷)

具有Tree BFS模式的問題：

• 二叉樹級順序遍歷(簡單)
• 鋸齒形遍歷(中)

8.樹DFS

樹DFS基于深度優(yōu)先搜索(DFS)技術(shù)遍歷樹。

您可以使用遞歸(或使用堆棧進行迭代)在遍歷時跟蹤所有先前的(父)節(jié)點。

Tree DFS模式通過從樹的根部開始工作，如果節(jié)點不是葉子，則需要做三件事：

• 決定是立即處理當(dāng)前節(jié)點(預(yù)訂)，還是在處理兩個子節(jié)點之間(按順序)，還是在處理兩個子節(jié)點之后(后處理)。
• 對當(dāng)前節(jié)點的兩個子節(jié)點進行兩次遞歸調(diào)用以處理它們。

如何識別Tree DFS模式：

• 如果系統(tǒng)要求您按順序，預(yù)定或后置DFS遍歷一棵樹
• 如果問題需要在節(jié)點更靠近葉子的位置進行搜索

具有Tree DFS模式的問題：

• 路徑數(shù)總和(中)
• 求和的所有路徑(中)

9.兩堆

在許多問題中，我們被賦予一組元素，以便可以將它們分為兩部分。 為了解決該問題，我們有興趣知道一個部分中的最小元素，而另一部分中的最大元素。 這種模式是解決此類問題的有效方法。

該模式使用兩個堆; 最小堆可查找最小元素，最大堆可查找最大元素。 該模式通過將數(shù)字的前半部分存儲在最大堆中而起作用，這是因為您要在前半部分中找到最大的數(shù)字。 然后，您想將數(shù)字的后半部分存儲在最小堆中，因為您希望在后半部分找到最小的數(shù)字。 在任何時候，都可以從兩個堆的頂部元素計算當(dāng)前數(shù)字列表的中位數(shù)。

識別兩個堆模式的方法：

• 在諸如"優(yōu)先級隊列"，"計劃"之類的情況下很有用
• 如果問題表明您需要找到集合中最小/最大/中值的元素
• 有時，對于解決具有二叉樹數(shù)據(jù)結(jié)構(gòu)的問題很有用

問題特點

• 查找數(shù)字流的中位數(shù)(中)

10.子集

大量的編碼面試問題涉及處理給定元素集的置換和組合。 模式子集描述了一種有效的廣度優(yōu)先搜索(BFS)方法來處理所有這些問題。

該模式如下所示：

給定一組[1、5、3]

• 從一個空集開始：[[]]
• 將第一個數(shù)字(1)添加到所有現(xiàn)有子集以創(chuàng)建新的子集：[[]，[1]];
• 將第二個數(shù)字(5)添加到所有現(xiàn)有子集：[[]，[1]，[5]，[1,5]];
• 將第三個數(shù)字(3)添加到所有現(xiàn)有子集：[[]，[1]，[5]，[1,5]，[3]，[1,3]，[5,3]，[1， 5,3]]。

這是子集模式的直觀表示：

 

 

如何識別子集模式：

• 您需要查找給定集合的組合或排列的問題

具有子集模式的問題：

• 重復(fù)子集(簡單)
• 更改大小寫的字符串排列(中)

11.修改后的二進制搜索

每當(dāng)給您排序數(shù)組，鏈接列表或矩陣，并且要求您查找某個元素時，可以使用的最佳算法是二進制搜索。 此模式描述了一種有效的方法來處理涉及二進制搜索的所有問題。

對于升序設(shè)置，模式如下所示：

• 首先，找到開始和結(jié)束的中間位置。 查找中間值的簡單方法是：middle =(start + end)/2。但這很有可能產(chǎn)生整數(shù)溢出，因此建議將中間值表示為：Middle = start +(end-start) / 2
• 如果鍵等于索引中間的數(shù)字，則返回中間
• 如果"鍵"不等于中間索引：
• 檢查鍵
• 檢查key> arr [middle]。 如果減少，則搜索結(jié)束=中間+1

這是"修改后的二進制搜索"模式的直觀表示：

 

 

具有修改后的二進制搜索模式的問題：

• 與訂單無關(guān)的二進制搜索(簡單)
• 在排序的無限數(shù)組中搜索

12.前K個元素

任何要求我們在給定集合中找到頂部/最小/頻率最高的" K"元素的問題都屬于此模式。

跟蹤" K"元素的最佳數(shù)據(jù)結(jié)構(gòu)是堆。 此模式將利用堆來解決一組給定元素中一次處理" K"元素的多個問題。 該模式如下所示：

• 根據(jù)問題將" K"元素插入最小堆或最大堆。
• 遍歷剩余的數(shù)字，如果發(fā)現(xiàn)一個大于堆中數(shù)字的數(shù)字，則刪除該數(shù)字并插入較大的數(shù)字。

 

 

不需要排序算法，因為堆將為您跟蹤元素。

如何識別最主要的" K"元素模式：

• 如果系統(tǒng)要求您查找給定集合中頂部/最小/頻繁的" K"元素
• 如果系統(tǒng)要求您對數(shù)組進行排序以查找確切的元素

出現(xiàn)" K"元素排行榜前的問題：

• 前" K"個數(shù)字(簡單)
• 前" K"個常見數(shù)字(中)

13. K-way合并

K-way Merge可幫助您解決涉及一組排序數(shù)組的問題。

只要獲得" K"個排序數(shù)組，就可以使用堆來有效地對所有數(shù)組的所有元素進行排序遍歷。 您可以將每個數(shù)組中的最小元素推入最小堆中，以獲取整體最小值。 獲得總最小值后，將下一個元素從同一數(shù)組推到堆中。 然后，重復(fù)此過程以對所有元素進行排序遍歷。

 

 

該模式如下所示：

• 將每個數(shù)組的第一個元素插入最小堆中。
• 之后，從堆中取出最小的(頂部)元素并將其添加到合并列表中。
• 從堆中刪除最小的元素后，將相同列表的下一個元素插入堆中。
• 重復(fù)步驟2和3，以按排序順序填充合并列表。

如何識別K-way合并模式：

• 該問題將出現(xiàn)排序的數(shù)組，列表或矩陣
• 如果問題要求您合并排序列表，請在排序列表中找到最小的元素。

K-way合并模式的問題：

• 合并K個排序列表(中)
• K對最大和(硬)

14.拓撲排序

拓撲排序用于查找相互依賴的元素的線性順序。 例如，如果事件" B"依賴于事件" A"，則按照拓撲順序，" A"排在" B"之前。

該模式定義了一種簡單的方法，可以理解用于對一組元素進行拓撲排序的技術(shù)。

該模式如下所示：

• 初始化a)使用HashMap將圖存儲在鄰接列表中b)要查找所有源，請使用HashMap保持度數(shù)
• 構(gòu)建圖并找到所有頂點的度數(shù)a)從輸入中構(gòu)建圖并填充度數(shù)HashMap。
• 查找所有源a)所有度數(shù)為" 0"的頂點將作為源，并存儲在隊列中。
• Sorta)對于每個來源，請執(zhí)行以下操作：—i)將其添加到排序列表中。 — ii)從圖中獲取其所有子級。 — iii)將每個孩子的度數(shù)減1。— iv)如果一個孩子的度數(shù)變?yōu)?quot; 0"，則將其添加到源隊列中。b)重復(fù)(a)，直到源隊列為空。

 

 

如何識別拓撲排序模式：

• 該問題將處理沒有定向周期的圖
• 如果系統(tǒng)要求您按排序順序更新所有對象
• 如果您有一類遵循特定順序的對象

具有拓撲排序模式的問題：

• 任務(wù)計劃(中)
• 最小樹高(硬)

接下來是什么?

遇到LeetCode疲勞嗎? 學(xué)習(xí)這14種模式，您將獲得關(guān)于如何解決問題的更全面的了解。

如果您想更深入地研究上述模式或每個模式下的示例問題，請查看《 Grokking編碼面試：編碼問題的模式》。 這是Grokking面試系列中的最新課程，有20,000多名學(xué)習(xí)者使用該課程在頂尖高科技公司找到工作。

我能給予的最高認可是，我真的希望當(dāng)我還在準備編寫編程面試時就已經(jīng)存在了。