最長回文子串 (Longest Palindromic Substring) 算是一個常考題。Palindrome 的定義是順讀逆讀,字母都一樣的詞語,比如範例給的 「 bab 」、 「 bb 」 等等,實際單字如 「 level 」 也是一個的 Palindromic 單字。

先熟悉「 Dynamic Programming - 2D matrix 」解和「 中心擴散法 (Expand Around Center) 」就好了,還有聽過最佳解 Manacher’s Algorithm,時間複雜度可優化到了 O(n)之後再花其他篇幅去補充

Continue reading

Heap 資料結構

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)的演算法中扮演極其重要的地位。

Continue reading

Author's picture

李昀陽 YunYang Lee

Welcome to my Tech Note. You can read some of the chapters below.

Software Engineer

Taiwan