今天是 30 天的最後一天，如昨天預告，慣例的第 30 天我都會做 30 天的內容整理與回顧。
今天讓我們來整理一下這 30 天到底都看了些什麼內容。

大綱

一開始我們條列了 30 天計畫大綱，最初列下的大綱包含：
資料結構

• 陣列(Array)
• 鏈結串列(Linked List)
• 矩陣(Matrix)
• 雜湊表(Hash Table)
• 佇列(Queue)和堆疊(Stack)
• 二元樹(Binary Tree)
• 圖論(Graph)

演算法為主題

• 貪心(Greedy)
• DFS / BFS
• BackTracking
• 動態規劃
• 雜項的特殊算法如位操作(Bit Manipulation)、數學運算等
  除去最後的雜項，其餘主題這 30 天都有介紹到，或許深淺不一，但作為敲門磚我想是足夠詳細，有些有就較高視角來展開該項主題的，也能幫助讀者快速回想特性與思考方式。

開始解題之前

在開始介紹上面主題之前，穿插了一篇「寫在開始解題之前」，是我個人覺得演算法之外，作為一個工程師應該在解決問題的時候注意到的細節。
如果是接觸程式還不久的人，我覺得讀一下可以比較自己的思考模式是否有遺漏，有些經驗的人可以自由選擇是否閱讀，可以比較你和我的思維模式是不是有哪裡不一樣，也歡迎分享你的想法。

資料結構主題

下面讓我就各篇的內容作快速的 Index 和連結，點選超連結都會直接連結到該篇文章

陣列 Array

特性 / Hint

• 易於檢索，難以插入
• 走訪順序
• 陣列本身有序無序(或可否排序)
• 元素有無重複、結果取用可否重複

相關演算法

• 雙指針
  • 快慢指針 - 處理循環陣列、起始條件差異，節省遍歷次數
  • 左右指針 - 透過左右指針往內收縮處理陣列元素遍歷，收縮表示選擇該向元素
• 滑動窗口 - 透過兩個指針維護指針中間的區域，依條件擴展或收縮指針，讓中間區域(連續元素)符合需求
• 前綴和 - 節省頻繁累加的狀況，透過前綴陣列的相減能求出特定連續區間和
• 差分陣列 - 頻繁對連續區間做處理，累計處理、一次套用
• 二分搜尋 - 有序無重複、以 O(log n) 的時間搜尋特定元素

題目實作 - 雙指針、滑動窗口
題目實作 - 前綴和、差分陣列、二分搜尋

矩陣 Matrix

本身結構

• 多數為二維陣列實踐
• 常見於圖論單元、表示圖的結構
• 遍歷方式如同訪問陣列，二維陣列透過雙重迴圈訪問，順向就是由左至右、由上至下
• 透過對角線的映射能讓行列索引交換，做到 in-place 的旋轉矩陣

鏈結串列 Linked-List

特性

• 易於插入，難於檢索
• 其餘基本要注意的特性 / hint 和陣列相同，一般關注於連續的元素 / 區間處理
• 分為單向鏈結串列和雙向鏈結串列、比例上單向比較多，如何記住 / 處理走過的元素避免回頭是重要的觀點
• 確認理解 CRUD 如何在鏈結串列的結構上實作

相關演算法

• 雙指針
• 單向鏈結串列的反轉(遞迴 / 迴圈)
• 有環無環結構檢測

題目實作 - CRUD、反轉單向鏈結串列、有環無環檢測

雜湊表 Hash Table

結構

• 常用於空間換取時間，記憶已算過的值(用 index / key 來 mapping)
• 實作結構選擇有 Array / Dictionary
• 選擇依據在於記憶 index / key 本身的複雜程度，單純單一情況下，用 Array 比較方便也省空間
• n Sum 的問題可以用這個來將時間複雜度降低一個指數級

佇列 Queue 與堆疊 Stack

結構

• 佇列 FIFO，基本方法 Enqueue、Dequeue、Peek
• 堆疊 FILO，基本方法 Push、Pop、Peek
• 練習互相模擬、了解結構替代 - 雙堆疊模擬一佇列、單佇列加上記憶最後放入(對堆疊而言)元素模擬單堆疊

延伸 1 - 單調堆疊 Monotonic Stack

• 單調性指的是單向遞增 / 遞減
• 用於解決特定問題類型：下一個更大 / 更小元素
• 關注的指示下一個更大 / 更小元素、透過僅在堆疊中保存可能變為該元素的元素來維持單調性(其餘排出)

延伸 2 - 單調佇列 Monotonic Queue

• 用於解決特定問題類型：滑動窗口最大值(滑動窗口持續滑度、求各滑動窗口區間內的單一最大值)，抽象化來說就是用低時間成本處理區間頻繁變動的最大值
• 佇列中只保留可能變成最大值的元素，當新元素加入導致其餘元素不會是最大值時直接排出
• 實際實作時會用雙向鏈結串列(C#中是LinkedList)，因為需要能夠移除尾端元素(Queue 本來只關注前頭元素)

二元樹 Binary Tree

結構

• n 元樹表示一個節點最多有 n 個子樹，二元樹中分別是左子樹和右子樹
• 名詞：根節點、父節點、子節點、葉節點、子樹、完全二元樹、滿二元樹
• 樹結構不能存在環

遍歷

• 前序、中序、後序，序指的是訪問發生時間點
• 依序是 中 - 左 - 右、左 - 中 - 右、左 - 右 - 中，也可以記必定先左後右，中的位置是 O 序就放在 O 的位置
• 中序特徵 - 二元搜尋樹用中序遍歷會剛好是小到大
• 後續特徵 - 回到中間節點時已經遍歷完左右，具備左右子樹的訊息
• 三序走訪偏向圖論中 DFS 的概念、深度優先，先走訪到葉節點為止，才逐層
• 層級遍歷則類似圖論中 BFS 的概念、廣度優先，以樹來說特徵在於從淺深度遍歷到比較深的節點，適合於處理橫向關係具有意義的問題

延伸 1 - 平衡二元樹 Balanced Binary Tree

• 關注樹的深度計算
• 平衡二元樹的定義是，任一左右子樹高度差異小於 1，利用這個定義透過遞迴來寫

延伸 2 - 二元搜尋樹 Binary Search Tree

查
刪改

• 二元搜尋樹的定義是，樹中任一節點，必定大於其左子樹所有節點和小於右子樹所有節點
• 中序遍歷為符合 BST 的遞增方向

延伸 3 - 回朔算法 Back Tracking

• 用樹的概念來說明選擇
• 回朔就是 DFS 的概念，從根結點持續往葉節點探索，每一次樹的分叉都是一個選擇
• 當累計的選擇已經不符需求的選擇條件時，往當前選擇的父節點回退，表示撤銷該選擇
• 明確剪枝概念來減少走訪的節點數量，節省時間

圖 Graph

特性

• 圖的題目表示有多種方式，通常是二維陣列或鏈結串列
• 抽象化來看，都可以說是由邊和節點構成
• 邊有無權重、有無方向
• 結構本身有環無環

遍歷

• 深度優先(DFS)
• 廣度優先(BFS)

延伸 1 - 最小生成樹(最低成本無向路徑)

• 基礎是併查集理論
• Kruskal : 依貪心理論選邊，選權重最小邊開始(排序後放入 Queue)，以 visited 陣列紀錄訪問過的點，當選定的邊數量等於節點 - 1 則結束
• Prim : 依貪心節點選點，從該點選擇可能路徑(放入 Priority Queue)，以 visited 陣列記錄訪問過的點，當所有點都被訪問過，就不會再放邊到待處理的陣列裡
• 無論哪種算法都倚賴邊的權重，如果題目沒有給邊長而是給座標，要先做邊長與點的關係集合才套上面演算法

延伸 2 - 有向圖最短路徑計算

• 無權的時候從起點開始，挑選任意邊，也是用 visited 陣列維持訪問過點的紀錄，類似 Prim 的感覺去把該點的可能邊拿出來，放入 Queue 依序處理
• Dijkstra 用於處理有向邊的權重挑選問題(有權)，變成用 Priority Queue 去存放以保證每次挑選的邊都從短的開始，維護一個陣列 arr[i]，意思是從起點到 i 的最短距離。因為有向有權的關係，無法保證第一次走到該點就是最短距離，需要遍歷所有路徑，每次持續比較是否目前走法比之前更短，持續更新為到 i 點的最短路徑長度

貪心算法 Greedy

概念

• 持續挑選局部最優解，期望得到全局最優解
• 只要選項間彼此會互相影響(選了 a 會導致不能選 b，且 b 可能更優)，就不會用貪心算法，反之，如果每個選項獨立，就可以試試

動態規劃 Dynamic Programming

步驟

• 首先，我們需要先定義問題中核心要求的數 - 確認狀態
• 了解該問題的關聯(遞增 / 遞減，挑選的邏輯) - 確認選擇(邏輯)
• 透過 1 與 2 的分析，去推出狀態轉移方程式，決定目標狀態如何被推導出來、下標涵義
• 狀態推導公式一般會需要基礎狀態才能夠開始不斷推導，確立初始值(如上面的狀態，)
• 確認於連續事件中狀態轉移方程式對資料源的遍歷方向(從前往後、從後往前、矩陣上到下...等等)
• 驗證推導結果，確定初始值

題目實作 - 矩陣路徑選擇、最長遞增子序列
題目實作 - BST排列種類

以上大概就是全部的 30 天的一步一腳印。

小結

總結正文大概至此結束，後面是自己的一些小心得。

一開始是希望能寫得盡量像陣列的單元，把每個資料結構題目做個總結、用比較高的角度來分析各個資料結構 / 主題類型的題目有什麼關鍵字能夠讓我們在作題目的時候，盡可能找到更多可能的切入點。
同時也就各個類型的題目挑一兩題代表的出來對照我們的討論，有實例對照會更清楚討論的點。

寫到後面其實覺得自己題目量寫的不夠多，很難每個主題都寫到自己滿意的程度，所以會看到 30 天的文章有不太一致的撰寫方式，也讓我自己覺得有點遺憾，有些章節寫得不夠完善，題目也可以挑的更好。
所以即使 30 天結束了，我也仍會繼續寫更多的題目，希望能讓自己的整體能力更加完善，也許有天，能夠把現在寫不好的地方，好好完善。有機會我也會再找地方放練習過程中覺得不錯 / 對我而言有啟發性的題目，再看看是不是補到這邊。

如果覺得我寫的這系列對你有幫助，歡迎訂閱起來，想看的時候就能回顧一下。
希望這 30 天的旅程，我們都和很多阿狗(Algorithm)交到朋友，在寫程式的這條路上，讓這些狗狗們讓我們有解決更多問題的能力，陪我們走得更遠一點。
謝謝所有支持、閱讀文章的讀者們，今年的 30 天旅程到此結束。