程式面試題庫

解題模式： 雙指標·複雜度： 時間 O(n)，空間 O(1)

在已排序陣列的兩端各放一個指標。總和太小就把左指標往右移，太大就把右指標往左移。因為陣列有序，保證你絕不會錯過任何一組有效的答案；面試官想聽你親口說出的，正是這個不變量。

解題模式： 雜湊表／計數·複雜度： 時間 O(n)；字母表固定時，空間 O(1)

先統計第一個字串的字元頻率，掃描第二個字串時逐一扣減，最後檢查所有計數是否都歸零。在被問到之前就主動提出延伸問題：如果要支援完整的 Unicode，固定 26 格的陣列就不夠用了，要改用雜湊表。

解題模式： Floyd 快慢指標·複雜度： 時間 O(n)，空間 O(1)

一個指標每次前進一個節點，另一個每次前進兩個；如果兩者相遇，就代表有環。準備好回答經典的延伸題：找出環的入口。把其中一個指標重設回 head，兩個指標都改成每次前進一步，再次相遇的地方就是入口。

解題模式： Boyer–Moore 投票演算法·複雜度： 時間 O(n)，空間 O(1)

維護一個候選值和一個計數器：遇到相同的就加一，不同的就減一，計數器歸零時就換掉候選值。因為多數元素出現超過 n/2 次，它一定會留到最後。解釋它「為什麼」一定會留下來，才是這場面試的重點。

解題模式： 單次掃描、維護目前最低價·複雜度： 時間 O(n)，空間 O(1)

記錄到目前為止看過的最低價，以及如果今天賣出能得到的最佳利潤。掃描一次，兩個變數就夠。這是「一路帶著最佳前綴狀態」這個概念最簡單的例子，之後會在 Kadane 演算法中再次出現；點出這個關聯會加分。

解題模式： 排序 + 線性掃描·複雜度： 時間 O(n log n)，空間 O(n)

先依起點排序區間，再依序掃描：如果目前區間的起點在上一個已合併區間的終點之後，就直接加入；否則就把合併後的終點延伸到兩者的最大值。真正發揮作用的是排序，要把這點說出來，並把比較時的邊界情況（端點相接的區間）處理正確。

解題模式： 雜湊集合 + 從序列起點開始·複雜度： 時間 O(n)，空間 O(n)

把所有數字放進一個集合；只從「前一個數不存在」的數字（也就是序列的起點）開始計數，再往後走。每個元素最多被拜訪兩次，面對「可是這裡有巢狀迴圈」的質疑時，這就是你捍衛 O(n) 的理由。

解題模式： 前綴積／後綴積·複雜度： 時間 O(n)；除了輸出之外，額外空間 O(1)

不用除法，掃描兩次：第一次在每一格填入它左邊所有元素的乘積，第二次從右邊往回掃，乘上它右邊所有元素的乘積。用除法的解法遇到 0 就會出錯，面試官通常也會明確禁止使用除法。

解題模式： 輔助堆疊的不變量·複雜度： 每次操作 O(1)，空間 O(n)

在存放數值的堆疊旁邊，再維護一個最小值堆疊，讓它的頂端永遠是底下所有元素的最小值：push 時放入 min(new, current top)，pop 時兩邊同步彈出。這是一道設計題，評分的是不變量，而不是程式碼的多寡。

解題模式： 雜湊表 + 雙向鏈結串列·複雜度： 每次 get/put O(1)，空間 O(capacity)

用雜湊表在 O(1) 時間內找到雙向鏈結串列中的節點，串列依最近使用的順序排列；存取時把節點移到頭部，超出容量時從尾部淘汰。用哨兵頭尾節點可以消除所有檢查 null 的邊界情況，在開始寫程式之前就先提出來。

解題模式： 網格 BFS/DFS 洪水填充·複雜度： 時間 O(rows × cols)

掃描整個網格；每遇到一個還沒拜訪過的陸地格子，就從它開始做洪水填充（DFS 或 BFS），把整座島標記為已拜訪，而你要計算的就是起點的數量。說明你標記已拜訪的策略（原地「淹沒」或另外用一個集合），以及超大網格的遞迴深度風險，這就是資深的訊號。

解題模式： 拓撲排序／環偵測·複雜度： 時間 O(V + E)

把先修關係建模成一張有向圖；「能不能修完所有課」這個問題，正好等於「這張圖有沒有環」。Kahn 演算法（反覆移除入度為 0 的節點）或 DFS 三色標記法都行，挑一個，並說明為什麼最後剩下節點就代表有環。

解題模式： BFS + 每層快照·複雜度： 時間 O(n)，空間 O(width)

用佇列做 BFS，但每一輪開始時先記下佇列的長度，這樣每一層就能輸出一個串列。這個「記下長度」的技巧是可以重複使用的核心：鋸齒形遍歷和右視圖，都是同一個迴圈，只是收集結果的步驟不同。

解題模式： 上下界傳遞／中序遍歷·複雜度： 時間 O(n)，空間 O(height)

遞迴時帶著一個允許的 (min, max) 範圍，每往下一層就收緊一次；或是做中序遍歷，檢查結果是否嚴格遞增。經典的陷阱是只拿子節點和父節點比較；在面試官提出反例之前，自己先把反例構造出來。

解題模式： 雙向雜湊映射（雙射）·複雜度： 時間 O(n)，空間 O(n)

把 pattern 的字元對應到單字，「同時」也把單字對應回字元；只做單向對應的話，pattern "ab" 會被誤判成符合 "dog dog"。雙向檢查雙射就是全部的訣竅；說出「雙射」這個詞，並在寫程式之前先處理長度不一致的情況。

解題模式： 在隱藏序列上偵測環·複雜度： 每一步 O(log n)；用 Floyd 演算法時空間 O(1)

反覆把一個數字換成它各位數字的平方和，最後不是到達 1，就是進入循環，所以這題其實是換了包裝的「環形鏈結串列」。用一個記錄看過數字的集合來偵測循環，或用 Floyd 快慢指標以 O(1) 空間讓人眼睛一亮。點出這題可以化約成環偵測，才是資深的做法。

解題模式： 需要證明的貪婪法·複雜度： 時間 O(n)，空間 O(1)

如果總油量 ≥ 總花費，答案就存在而且唯一。掃描一次並追蹤目前油箱的油量；每當油量變成負數，失敗的那一段中任何一站都不可能是起點，就從下一站重新開始。這題面試的重點是說明為什麼可以這樣跳過，而不是迴圈本身。

解題模式： 貪婪法／隱式 BFS 分層·複雜度： 時間 O(n)，空間 O(1)

把 k 次跳躍內能到達的索引視為 BFS 的一層：追蹤目前這一層的右邊界，以及目前看到能到達的最遠位置；走過右邊界時，跳躍次數加一，並把邊界延伸到那個最遠位置。把它說成「不用佇列的 BFS」，就能解釋貪婪法在這裡「為什麼」是最佳解。

解題模式： 三階段線性合併·複雜度： 時間 O(n)，空間 O(n)

先輸出在新區間開始前就結束的區間，再把所有重疊的區間併入新區間（取最小的起點和最大的終點），最後輸出剩下的區間。因為輸入已經排序，只要掃描一次、不必重新排序；如果被問到為什麼這題比較簡單，就拿它和「合併區間」比較。

解題模式： 原地矩陣變換·複雜度： 時間 O(n²)，空間 O(1)

順時針旋轉 90° = 先轉置，再把每一橫列反轉。兩次乾淨的掃描、O(1) 額外空間，勝過在壓力下手推四方向的循環交換；但如果面試官不滿足於這個技巧，要準備好解釋座標對應 (i,j) → (j, n−1−i)。

解題模式： 借用既有空間的原地標記·複雜度： 時間 O(m×n)，空間 O(1)

用第一橫列和第一直行當作旗標儲存區，記錄哪些橫列和直行要歸零，再用兩個布林值記住它們自己原本的狀態。把空間複雜度的階梯大聲說一遍：O(mn) 複製 → O(m+n) 集合 → O(1) 借用空間，因為這個階梯本身就是考點。

解題模式： 排序／計數桶·複雜度： 排序法 O(n log n)，計數桶 O(n)

由大到小排序，找出滿足 citations[i] ≥ i+1 的最大 i；或者不排序，改用上限為 n 的計數桶，做到 O(n)。寫程式之前先精確說出定義；這題大多數的失誤都是誤讀了「有 h 篇論文至少被引用 h 次」，而不是演算法本身。

解題模式： 拓撲排序並輸出順序·複雜度： 時間 O(V + E)

和「課程表」是同一張圖，但這次 Kahn 演算法真正派上用場：入度為 0 的節點離開佇列的順序，「就是」一個合法的修課順序。如果輸出的順序比課程數少，就代表有環，回傳空陣列。也提一下另一種做法：把 DFS 後序遍歷的結果反轉。

解題模式： 滑動視窗 + 滿足條件計數器·複雜度： 時間 O(n)，空間 O(alphabet)

擴張右邊界，直到視窗涵蓋所有需要的字元（追蹤一個「已滿足 vs. 需要」的計數器，而不是每一步都比對整張表），再在仍然有效的前提下把左邊界收縮到最小，並記錄最佳結果。這個「已滿足計數器」的優化是讓它維持 O(n) 的關鍵，要明確解釋出來。

解題模式： 雙指標 + 左右目前最大值·複雜度： 時間 O(n)，空間 O(1)

每根柱子上方的水量是 min(max-left, max-right) − height。兩個指標從兩端往內移動，每次處理目前最大值比較低的那一側，因為那一側的上界已經確定了。把這個確定性為什麼成立講清楚，這就是整道題的核心。