↓推薦關注↓

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

讓我們開始吧！

解題套路

咱們在面試程序員崗位時往往需要經歷一個編程面試過程，雇主會借此考驗面試者的技術實力。

然而，這些技術問題有時候卻和我們的實際工作并無太大關系，也由此可能給我們的編程面試準備階段帶來很大的壓力。

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

對很多開發(fā)者來說，編程工作的面試準備很容易讓人焦慮。面試要涉及的東西實在太多，其中很多還往往與開發(fā)者的日常工作無關，只會額外增添壓力。

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

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

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

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

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

另外我還會說明如何識別每種模式，并會為每種模式提供一些問題示例。

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

下面的模式說明假設你已經知悉了數(shù)據(jù)結構。如果你還不了解，那需要補充一下知識點哦。

我們今天將說明以下 14 種模式：

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

我們開始吧！

1．滑動窗口

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

從第一個元素開始滑動窗口并逐個元素地向右滑，并根據(jù)你所求解的問題調整窗口的長度。

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

下面是一些你可以用來確定給定問題可能需要滑動窗口的方法：

• 問題的輸入是一種線性數(shù)據(jù)結構，比如鏈表、數(shù)組或字符串
• 你被要求查找最長/最短的子字符串、子數(shù)組或所需的值

你可以使用滑動窗口模式處理的常見問題：

• 大小為 K 的子數(shù)組的最大和（簡單）
• 帶有 K 個不同字符的最長子字符串（中等）
• 尋找字符相同但排序不一樣的字符串（困難）

2．二指針或迭代器

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

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

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

二指針是很有用的，因為如果只有一個指針，你必須繼續(xù)在數(shù)組中循環(huán)回來才能找到答案。

這種使用單個迭代器進行來回在時間和空間復雜度上都很低效——這個概念被稱為「漸進分析（asymptotic analysis）」。

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

用于識別使用二指針的時機的方法：

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

下面是一些滿足二指針模式的問題：

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

3．快速和慢速指針

快速和慢速指針方法也被稱為 Hare