這題需求是要合併 k 個 linked-list 成一個大的 linked-list,每個 linked-list 都是有序的,且大的 linked-list 也必須是有序的,是 LeetCode21. Merge Two Sorted Lists 的進階題,但本題可用 min heap 解題,還蠻巧妙的,故紀錄一下。


這題需求是要合併 k 個 linked-list 成一個大的 linked-list,每個 linked-list 都是有序的,且大的 linked-list 也必須是有序的,是 LeetCode21. Merge Two Sorted Lists 的進階題,但本題可用 min heap 解題,還蠻巧妙的,故紀錄一下。

LeetCode21. Merge Two Sorted Lists這道題目主要是熟悉 linked-list 相關重點,例如:
- dummy head
- 當新 Linked List 加完所有的節點後,需要返回其頭節點的 next,即
dummy.next這些技巧在後續解決 Linked List 題目時會反覆用到。

最長回文子串 (Longest Palindromic Substring) 算是一個常考題。Palindrome 的定義是順讀逆讀,字母都一樣的詞語,比如範例給的 「 bab 」、 「 bb 」 等等,實際單字如 「 level 」 也是一個的 Palindromic 單字。
先熟悉「 Dynamic Programming - 2D matrix 」解和「 中心擴散法 (Expand Around Center) 」就好了,還有聽過最佳解 Manacher’s Algorithm,時間複雜度可優化到了 O(n),之後再花其他篇幅去補充。

Heap 的定義是「 父節點和子節點之間滿足固定大小關係的 Tree 」,當所有父節點都大於其子節點時,就稱其為「Max Heap」; 當所有父節點都小於其子節點時,就稱其為「Min Heap」,附上一個 Heap 圖參考連結。 Heap 本身定義上只關心節點之間的順序規則,所以可以有很多種類例如: d-ary heap、binomial heap、Fibonacci heap 等等,但很多時候教材講的 Heap,其實默認會是 complete binary heap ,也就是除了滿足 heap property 還滿足了:
- complete: 代表同一階層要由左到右排列,不能跳過
- binary: 每個 node 最多只能有兩個 child
Heap 常被作為 Priority Queue 的實作方式,且在一些圖論(例如 Dijkstra)或排序(Heap sort)的演算法中扮演極其重要的地位。

Stack 是一種「後進先出 LIFO」的容器 (Last if First Out),適用於需要紀錄之前的狀態或是值的情況,必要的時候可以回到之前的樣子。對於 Java 和 Python 的 Stack 使用可以記憶一下:
- Java 推薦是雙端隊列 Deque 取代 Stack
- Python 更簡單的可直接將 List 作為 Stack 使用

