本篇內(nèi)容主要講解“Grokking編碼模式有哪些”，感興趣的朋友不妨來(lái)看看。本文介紹的方法操作簡(jiǎn)單快捷，實(shí)用性強(qiáng)。下面就讓小編來(lái)帶大家學(xué)習(xí)“Grokking編碼模式有哪些”吧!

成都創(chuàng)新互聯(lián)公司專注于企業(yè)成都全網(wǎng)營(yíng)銷推廣、網(wǎng)站重做改版、屯昌網(wǎng)站定制設(shè)計(jì)、自適應(yīng)品牌網(wǎng)站建設(shè)、H5響應(yīng)式網(wǎng)站、商城網(wǎng)站開發(fā)、集團(tuán)公司官網(wǎng)建設(shè)、外貿(mào)網(wǎng)站建設(shè)、高端網(wǎng)站制作、響應(yīng)式網(wǎng)頁(yè)設(shè)計(jì)等建站業(yè)務(wù)，價(jià)格優(yōu)惠性價(jià)比高，為屯昌等各大城市提供網(wǎng)站開發(fā)制作服務(wù)。

1.推拉窗

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

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

• 問(wèn)題輸入是線性數(shù)據(jù)結(jié)構(gòu)，例如鏈表，數(shù)組或字符串

• 要求您找到最長(zhǎng)/最短的子字符串，子數(shù)組或所需的值

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

• 大小為" 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è)迭代器來(lái)回進(jìn)行此操作對(duì)于時(shí)間和空間復(fù)雜度而言效率低下-一種稱為漸近分析的概念。  盡管使用1個(gè)指針的強(qiáng)力或樸素的解決方案將起作用，但它會(huì)產(chǎn)生類似于O(n²)的線。  在許多情況下，兩個(gè)指針可以幫助您找到具有更好空間或運(yùn)行時(shí)復(fù)雜性的解決方案。

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

• 在處理排序數(shù)組(或鏈接列表)并且需要找到一組滿足某些約束的元素時(shí)，它將遇到一些問(wèn)題。

• 數(shù)組中的元素集是一對(duì)，三元組甚至是子數(shù)組

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

• 平方排序數(shù)組(簡(jiǎn)單)

• 總計(jì)為零的三元組(中)

• 比較包含退格鍵的字符串(中)

3.快速和慢速指針

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

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

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

• 該問(wèn)題將處理鏈表或數(shù)組中的循環(huán)

• 當(dāng)您需要知道某個(gè)元素的位置或鏈表的總長(zhǎng)度時(shí)。

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

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

具有快速和慢速指針模式的問(wèn)題：

• 鏈接列表周期(簡(jiǎn)單)

• 回文鏈接列表(中)

• 循環(huán)循環(huán)陣列(硬)

4.合并間隔

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

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

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

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

• 如果要求您僅以互斥間隔生成列表

• 如果您聽到術(shù)語(yǔ)"重疊間隔"。

合并間隔問(wèn)題模式：

• 區(qū)間相交(中)

• 最大CPU負(fù)載(硬)

5.循環(huán)排序

此模式描述了一種有趣的方法來(lái)處理涉及包含給定范圍內(nèi)的數(shù)字的數(shù)組的問(wèn)題。  循環(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ù)組的問(wèn)題

• 如果問(wèn)題要求您在排序/旋轉(zhuǎn)數(shù)組中查找缺失/重復(fù)/最小的數(shù)字

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

• 查找丟失的號(hào)碼(簡(jiǎn)單)

• 查找最小的遺漏正數(shù)(中)

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

在很多問(wè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)。  以鎖定步驟的方式，您可以通過(guò)將當(dāng)前節(jié)點(diǎn)指向上一個(gè)節(jié)點(diǎn)來(lái)反轉(zhuǎn)該節(jié)點(diǎn)，然后再移動(dòng)到下一個(gè)節(jié)點(diǎn)。 另外，您將更新變量"  previous"以始終指向您已處理的上一個(gè)節(jié)點(diǎn)。

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

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

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

• 撤消子列表(中)

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

7.樹BFS

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

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

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

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

具有Tree BFS模式的問(wèn)題：

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

• 鋸齒形遍歷(中)

8.樹DFS

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

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

Tree DFS模式通過(guò)從樹的根部開始工作，如果節(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遍歷一棵樹

• 如果問(wèn)題需要在節(jié)點(diǎn)更靠近葉子的位置進(jìn)行搜索

具有Tree DFS模式的問(wèn)題：

• 路徑數(shù)總和(中)

• 求和的所有路徑(中)

9.兩堆

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

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

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

• 在諸如"優(yōu)先級(jí)隊(duì)列"，"計(jì)劃"之類的情況下很有用

• 如果問(wèn)題表明您需要找到集合中最小/最大/中值的元素

• 有時(shí)，對(duì)于解決具有二叉樹數(shù)據(jù)結(jié)構(gòu)的問(wèn)題很有用

問(wèn)題特點(diǎn)

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

10.子集

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

該模式如下所示：

給定一組[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í)別子集模式：

• 您需要查找給定集合的組合或排列的問(wèn)題

具有子集模式的問(wèn)題：

• 重復(fù)子集(簡(jiǎn)單)

• 更改大小寫的字符串排列(中)

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

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

• 與訂單無(wú)關(guān)的二進(jìn)制搜索(簡(jiǎn)單)

• 在排序的無(wú)限數(shù)組中搜索

12.前K個(gè)元素

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

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

• 根據(jù)問(wèn)題將" 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"元素排行榜前的問(wèn)題：

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

• 前" K"個(gè)常見數(shù)字(中)

13. K-way合并

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

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

該模式如下所示：

• 將每個(gè)數(shù)組的第一個(gè)元素插入最小堆中。

• 之后，從堆中取出最小的(頂部)元素并將其添加到合并列表中。

• 從堆中刪除最小的元素后，將相同列表的下一個(gè)元素插入堆中。

• 重復(fù)步驟2和3，以按排序順序填充合并列表。

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

• 該問(wèn)題將出現(xiàn)排序的數(shù)組，列表或矩陣

• 如果問(wèn)題要求您合并排序列表，請(qǐng)?jiān)谂判蛄斜碇姓业阶钚〉脑亍?/p>

K-way合并模式的問(wèn)題：

• 合并K個(gè)排序列表(中)

• K對(duì)最大和(硬)

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

拓?fù)渑判蛴糜诓檎蚁嗷ヒ蕾嚨脑氐木€性順序。 例如，如果事件" B"依賴于事件" A"，則按照拓?fù)漤樞颍? 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è)來(lái)源，請(qǐng)執(zhí)行以下操作：—i)將其添加到排序列表中。 — ii)從圖中獲取其所有子級(jí)。 — iii)將每個(gè)孩子的度數(shù)減1。—  iv)如果一個(gè)孩子的度數(shù)變?yōu)? 0"，則將其添加到源隊(duì)列中。b)重復(fù)(a)，直到源隊(duì)列為空。

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

• 該問(wèn)題將處理沒有定向周期的圖

• 如果系統(tǒng)要求您按排序順序更新所有對(duì)象

• 如果您有一類遵循特定順序的對(duì)象

具有拓?fù)渑判蚰Ｊ降膯?wèn)題：

• 任務(wù)計(jì)劃(中)

• 最小樹高(硬)

到此，相信大家對(duì)“Grokking編碼模式有哪些”有了更深的了解，不妨來(lái)實(shí)際操作一番吧！這里是創(chuàng)新互聯(lián)網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！