↓推薦關(guān)注↓

貌似2022屆校招提前批已經(jīng)快開始了，現(xiàn)在不管是校招還是社招算法題肯定會(huì)被考察到，要么讓你手寫代碼，要么在線做題。這篇文章關(guān)于常見的算法解題套路，總結(jié)了 14 種算法模式，講的挺好的。

讓我們開始吧！

解題套路

咱們?cè)诿嬖嚦绦騿T崗位時(shí)往往需要經(jīng)歷一個(gè)編程面試過(guò)程，雇主會(huì)借此考驗(yàn)面試者的技術(shù)實(shí)力。

然而，這些技術(shù)問(wèn)題有時(shí)候卻和我們的實(shí)際工作并無(wú)太大關(guān)系，也由此可能給我們的編程面試準(zhǔn)備階段帶來(lái)很大的壓力。

曾在 Facebook 和微軟工作過(guò)的 Educative.io 創(chuàng)始人 Fahim ul Haq 近日發(fā)文總結(jié)了編程面試所遇到的問(wèn)題的 14 種最常見的模式，也許能幫你看清各種編程面試問(wèn)題「背后的真相」。

對(duì)很多開發(fā)者來(lái)說(shuō)，編程工作的面試準(zhǔn)備很容易讓人焦慮。面試要涉及的東西實(shí)在太多，其中很多還往往與開發(fā)者的日常工作無(wú)關(guān)，只會(huì)額外增添壓力。

這種現(xiàn)狀導(dǎo)致了一個(gè)后果：現(xiàn)在的開發(fā)者往往需要花費(fèi)數(shù)周時(shí)間在 LeetCode 等網(wǎng)站上了解綜合數(shù)百個(gè)問(wèn)題。

與我談過(guò)的開發(fā)者在面試前的一個(gè)常見焦慮問(wèn)題是：我是否已經(jīng)解決過(guò)足夠多的實(shí)際問(wèn)題？我本可以做到更多嗎？

這就是我想要幫助開發(fā)者了解每個(gè)問(wèn)題背后的底層模式的原因——這樣他們就不必?fù)?dān)憂解決數(shù)百個(gè)問(wèn)題以及被 LeetCode 整得疲憊不堪了。

如果你理解面試的通用模式，你就可以將其用作模板，從而解決各種層級(jí)的稍有不同的問(wèn)題。

這里我將列出最常見的 14 種模式，它們可被用于解決任何編程面試問(wèn)題。

另外我還會(huì)說(shuō)明如何識(shí)別每種模式，并會(huì)為每種模式提供一些問(wèn)題示例。

這些內(nèi)容都只是蜻蜓點(diǎn)水——我強(qiáng)烈建議你看看課程《Grokking the Coding Interview: Patterns for Coding Questions》，里面提供了全面的解釋、示例和編程實(shí)踐。

下面的模式說(shuō)明假設(shè)你已經(jīng)知悉了數(shù)據(jù)結(jié)構(gòu)。如果你還不了解，那需要補(bǔ)充一下知識(shí)點(diǎn)哦。

我們今天將說(shuō)明以下 14 種模式：

• 1．滑動(dòng)窗口
• 2．二指針或迭代器
• 3．快速和慢速指針或迭代器
• 4．合并區(qū)間
• 5．循環(huán)排序
• 6．原地反轉(zhuǎn)鏈表
• 7．樹的寬度優(yōu)先搜索（Tree BFS）
• 8．樹的深度優(yōu)先搜索（Tree DFS）
• 9．Two Heaps
• 10．子集
• 11．經(jīng)過(guò)修改的二叉搜索
• 12．前 K 個(gè)元素
• 13．K 路合并
• 14．拓?fù)渑判?/li>

我們開始吧！

1．滑動(dòng)窗口

滑動(dòng)窗口模式是用于在給定數(shù)組或鏈表的特定窗口大小上執(zhí)行所需的操作，比如尋找包含所有 1 的最長(zhǎng)子數(shù)組。

從第一個(gè)元素開始滑動(dòng)窗口并逐個(gè)元素地向右滑，并根據(jù)你所求解的問(wèn)題調(diào)整窗口的長(zhǎng)度。

在某些情況下窗口大小會(huì)保持恒定，在其它情況下窗口大小會(huì)增大或減小。

下面是一些你可以用來(lái)確定給定問(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．二指針或迭代器

二指針（Two Pointers）是這樣一種模式：

兩個(gè)指針以一前一后的模式在數(shù)據(jù)結(jié)構(gòu)中迭代，直到一個(gè)或兩個(gè)指針達(dá)到某種特定條件。

二指針通常在排序數(shù)組或鏈表中搜索配對(duì)時(shí)很有用：比如當(dāng)你必須將一個(gè)數(shù)組的每個(gè)元素與其它元素做比較時(shí)。

二指針是很有用的，因?yàn)槿绻挥幸粋€(gè)指針，你必須繼續(xù)在數(shù)組中循環(huán)回來(lái)才能找到答案。

這種使用單個(gè)迭代器進(jìn)行來(lái)回在時(shí)間和空間復(fù)雜度上都很低效——這個(gè)概念被稱為「漸進(jìn)分析（asymptotic analysis）」。

盡管使用 1 個(gè)指針進(jìn)行暴力搜索或簡(jiǎn)單普通的解決方案也有效果，但這會(huì)沿 O(n2) 線得到一些東西。在很多情況中，二指針有助于你尋找有更好空間或運(yùn)行時(shí)間復(fù)雜度的解決方案。

用于識(shí)別使用二指針的時(shí)機(jī)的方法：

• 可用于你要處理排序數(shù)組（或鏈接列表）并需要查找滿足某些約束的一組元素的問(wèn)題
• 數(shù)組中的元素集是配對(duì)、三元組甚至子數(shù)組

下面是一些滿足二指針模式的問(wèn)題：

• 求一個(gè)排序數(shù)組的平方（簡(jiǎn)單）
• 求總和為零的三元組（中等）
• 比較包含回退（backspace）的字符串（中等）

3．快速和慢速指針

快速和慢速指針?lè)椒ㄒ脖环Q為 Hare