[[325909]]

 

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

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

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

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

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

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

• 滑動(dòng)窗口
• 2個(gè)指針或迭代器
• 快指針或慢指針或迭代器
• 合并間隔
• 循環(huán)排序
• 就地反轉(zhuǎn)鏈表
• 樹BFS
• 樹DFS
• 兩堆
• 子集
• 修改后的二進(jìn)制搜索
• 前K個(gè)元素
• K路合并
• 拓?fù)渑判?/li>

讓我們開始吧!

1.推拉窗

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

 

 

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

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

您將滑動(dòng)窗口模式用于以下常見問題：

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

2.兩個(gè)指針或迭代器

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

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

 

 

確定何時(shí)使用"兩指針"方法的方法：

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

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

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

3.快速和慢速指針

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

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

 

 

您如何確定何時(shí)使用快速和慢速模式?

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

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

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

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

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

4.合并間隔

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

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

 

 

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

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

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

合并間隔問題模式：

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

5.循環(huán)排序

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

 

 

如何識(shí)別這種模式?

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

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

• 查找丟失的號(hào)碼(簡(jiǎn)單)
• 查找最小的遺漏正數(shù)(中)

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

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

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

 

 

如何確定何時(shí)使用此模式：

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

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

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

7.樹BFS

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

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

如何識(shí)別Tree BFS模式：

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

具有Tree BFS模式的問題：

• 二叉樹級(jí)順序遍歷(簡(jiǎn)單)
• 鋸齒形遍歷(中)

8.樹DFS

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

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

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

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

如何識(shí)別Tree DFS模式：

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

具有Tree DFS模式的問題：

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

9.兩堆

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

該模式使用兩個(gè)堆; 最小堆可查找最小元素，最大堆可查找最大元素。 該模式通過將數(shù)字的前半部分存儲(chǔ)在最大堆中而起作用，這是因?yàn)槟谇鞍氩糠种姓业阶畲蟮臄?shù)字。 然后，您想將數(shù)字的后半部分存儲(chǔ)在最小堆中，因?yàn)槟Ｍ诤蟀氩糠终业阶钚〉臄?shù)字。 在任何時(shí)候，都可以從兩個(gè)堆的頂部元素計(jì)算當(dāng)前數(shù)字列表的中位數(shù)。

識(shí)別兩個(gè)堆模式的方法：

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

問題特點(diǎn)

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

10.子集

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

該模式如下所示：

給定一組[1、5、3]

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

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

 

 

如何識(shí)別子集模式：

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

具有子集模式的問題：

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

11.修改后的二進(jìn)制搜索

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

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

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

這是"修改后的二進(jìn)制搜索"模式的直觀表示：

 

 

具有修改后的二進(jìn)制搜索模式的問題：

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

12.前K個(gè)元素

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

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

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

 

 

不需要排序算法，因?yàn)槎褜槟櫾亍?/p>

如何識(shí)別最主要的" K"元素模式：

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

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

• 前" K"個(gè)數(shù)字(簡(jiǎn)單)
• 前" K"個(gè)常見數(shù)字(中)

13. K-way合并

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

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

 

 

該模式如下所示：

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

如何識(shí)別K-way合并模式：

• 該問題將出現(xiàn)排序的數(shù)組，列表或矩陣
• 如果問題要求您合并排序列表，請(qǐng)?jiān)谂判蛄斜碇姓业阶钚〉脑亍?/li>

K-way合并模式的問題：

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

14.拓?fù)渑判?/strong>

拓?fù)渑判蛴糜诓檎蚁嗷ヒ蕾嚨脑氐木€性順序。 例如，如果事件" B"依賴于事件" A"，則按照拓?fù)漤樞颍?quot; A"排在" B"之前。

該模式定義了一種簡(jiǎn)單的方法，可以理解用于對(duì)一組元素進(jìn)行拓?fù)渑判虻募夹g(shù)。

該模式如下所示：

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

 

 

如何識(shí)別拓?fù)渑判蚰Ｊ剑?/p>

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

具有拓?fù)渑判蚰Ｊ降膯栴}：

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

接下來是什么?

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

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

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