[[325909]]

 

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

結果之一是，開發人員現在通常花數周的時間在LeetCode等網站上瀏覽數百個面試問題。 在面試之前，我談到的焦慮癥開發人員最常見的觀點之一是：我是否解決了足夠的練習題? 我還能做更多嗎?

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

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

以下模式假定您已經精通數據結構。 如果還沒有的話，請查看這些有關數據結構的復習課程。

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

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

讓我們開始吧!

1.推拉窗

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

 

 

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

• 問題輸入是線性數據結構，例如鏈表，數組或字符串
• 要求您找到最長/最短的子字符串，子數組或所需的值

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

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

2.兩個指針或迭代器

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

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

 

 

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

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

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

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

3.快速和慢速指針

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

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

 

 

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

• 該問題將處理鏈表或數組中的循環
• 當您需要知道某個元素的位置或鏈表的總長度時。

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

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

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

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

4.合并間隔

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

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

 

 

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

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

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

合并間隔問題模式：

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

5.循環排序

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

 

 

如何識別這種模式?

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

具有循環排序模式的問題：

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

6.就地反轉鏈表

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

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

 

 

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

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

鏈表模式就地反轉的問題：

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

7.樹BFS

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

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

如何識別Tree BFS模式：

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

具有Tree BFS模式的問題：

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

8.樹DFS

樹DFS基于深度優先搜索(DFS)技術遍歷樹。

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

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

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

如何識別Tree DFS模式：

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

具有Tree DFS模式的問題：

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

9.兩堆

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

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

識別兩個堆模式的方法：

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

問題特點

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

10.子集

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

該模式如下所示：

給定一組[1、5、3]

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

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

 

 

如何識別子集模式：

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

具有子集模式的問題：

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

11.修改后的二進制搜索

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

對于升序設置，模式如下所示：

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

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

 

 

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

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

12.前K個元素

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

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

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

 

 

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

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

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

出現" K"元素排行榜前的問題：

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

13. K-way合并

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

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

 

 

該模式如下所示：

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

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

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

K-way合并模式的問題：

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

14.拓撲排序

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

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

該模式如下所示：

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

 

 

如何識別拓撲排序模式：

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

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

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

接下來是什么?

遇到LeetCode疲勞嗎? 學習這14種模式，您將獲得關于如何解決問題的更全面的了解。

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

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