> For the complete documentation index, see [llms.txt](https://jenhsuan.gitbook.io/algorithm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jenhsuan.gitbook.io/algorithm/leetcode.md).

# Leetcode

The records of self practices for Leetcode challenges

## 1.Performance

### [上界與下界](https://jenhsuan.gitbook.io/algorithm/notes-of-algorithms/asymptotic-notation)

* Big-Theta (Θ): asymptotic **tight** bound 
  *  Θ(g(n)) = { 存在有positive constant c1, c2, n0, 使f(n) 滿足0 ≤ c1g(n) ≤ f(n) ≤ c2g(n), n >= n0}
* Big-O (O): asymptotic **upper** bound
  *  O(g(n)) = { 存在有positive constant c, n0, 使f(n) 滿足0 ≤ f(n) ≤ cg(n), n >= n0}
* Big-Omega (Ω): asymptotic **lower** bound
  *  Ω(g(n)) = { 存在有positive constant c, n0, 使f(n) 滿足0 ≤ cg(n) ≤ f(n), n >= n0}

### 效能項目集

* 常數 constant: O(1)
* 對數 logarithmic: O(log n)

> e.g., 猜測演算法 (guess),  二分法 (bisection)

* 次線性 sublinear: O(n ^ d), d < 1

> e.g., k-d tree

* 線性 linear: O(n)

> e.g.,addition

* 線性對數 linearithmic: O(n log n)

> e.g., divide and conquer

* 二次方 quadratic: O(n^2)
* 指數 exponential: O(2^n)

## 2.Algorithm

### \[1.分治法 Divide and Conquer]

> 分為解析 (真正處理問題的程序)以及以及遞迴, 如果解析需要O(n)時間, 則每次都分為兩半則總共需要O(n log n)時間

### \[2.動態規劃法 Dynamic programming]

* [198.House Robber (Easy)](https://jenhsuan.gitbook.io/algorithm/leetcode/198.-house-robber-easy)
* [213.House Robber II (Medium)](https://jenhsuan.gitbook.io/algorithm/leetcode/213.-house-robber-ii-medium)
* [337.House Robber III (Medium)](https://jenhsuan.gitbook.io/algorithm/leetcode/337.-house-robber-iii-medium)
* [174.Dungeon Game (Hard)](https://jenhsuan.gitbook.io/algorithm/leetcode/174.-dungeon-game-hard)

## 3.Data Structure

### \[Overview]

| Data structure                                                                                          | Access           | Search                    | Insertion                 | Deletion                  | Properties                                                                                                                                                            |
| ------------------------------------------------------------------------------------------------------- | ---------------- | ------------------------- | ------------------------- | ------------------------- | --------------------------------------------------------------------------------------------------------------------------------------------------------------------- |
| [Binary heap](https://jenhsuan.gitbook.io/algorithm/algorithms-in-a-nutshell/binary-heap)               | O(1)             | O(log n)                  | O(log n)                  | O(log n)                  | <p><strong>A</strong>:直接索引</p><p><strong>S</strong>: log n層</p><p><strong>I</strong>:插到最後, sift up</p><p><strong>D</strong>:移除root, 將最大值移到root後sift down root</p>     |
| Hash table                                                                                              | NA               | <p>O(1) \~</p><p>O(n)</p> | <p>O(1) \~</p><p>O(n)</p> | <p>O(1) \~</p><p>O(n)</p> | <p><strong>A</strong>:無法索引<br><strong>S:</strong> 必須用Key索引<br><strong>I:</strong> 計算hash值後插入<br><strong>D</strong>:計算hash值後移除</p><p><strong>W: collision</strong></p> |
| [Stack](https://jenhsuan.gitbook.io/algorithm/algorithms-in-a-nutshell/stack)                           | O(n)             | O(n)                      | O(1)                      | O(1)                      | <p><strong>A</strong>:必須循覽整個序列<br><strong>S</strong>:必須循覽整個序列<br><strong>I</strong>:push到最上方<br><strong>D:</strong>pop最上方元素</p>                                       |
| [Queue](https://jenhsuan.gitbook.io/algorithm/algorithms-in-a-nutshell/queue)                           | O(n)             | O(n)                      | O(1)                      | O(1)                      | <p><strong>A</strong>:必須循覽整個序列 <br><strong>S</strong>:必須循覽整個序列</p><p><strong>I:</strong>從後方enque <br><strong>D</strong>:dequeue最前方元素</p>                              |
| [Single linked list](https://jenhsuan.gitbook.io/algorithm/algorithms-in-a-nutshell/linked-list)        | O(n)             | O(n)                      | O(1)                      | O(1)                      | <p><strong>A:</strong>必須循覽整個序列 </p><p><strong>S:</strong>必須循覽整個序列 </p>                                                                                                |
| [Doubly linked list](https://jenhsuan.gitbook.io/algorithm/algorithms-in-a-nutshell/doubly-linked-list) | O(n)             | O(n)                      | O(1)                      | O(1)                      | <p><strong>A</strong>:必須循覽整個序列 </p><p><strong>S</strong>:必須循覽整個序列</p>                                                                                                 |
| [Array](https://jenhsuan.gitbook.io/algorithm/algorithms-in-a-nutshell/pointer-and-array)               | O(1)             | O(n)                      | O(n)                      | O(n)                      | <p><strong>A</strong>:直接索引 <br><strong>S, I, D</strong>:必須循覽整個序列 </p>                                                                                                 |
| Binary Search Tree                                                                                      | O(log n) \~ O(n) | O(log n) \~ O(n)          | O(log n) \~ O(n)          | O(log n) \~ O(n)          | <p>必須循覽整個序列</p><p><strong>W: unbalance</strong></p>                                                                                                                   |
| Balance Binary Search Tree                                                                              | O(log n)         | O(log n)                  | O(log n)                  | O(log n)                  | 必須循覽整個序列                                                                                                                                                              |
| AVL Tree                                                                                                | O(log n)         | O(log n)                  | O(log n)                  | O(log n)                  | 必須循覽整個序列                                                                                                                                                              |
| B-Tree                                                                                                  | O(log n)         | O(log n)                  | O(log n)                  | O(log n)                  | 必須循覽整個序列                                                                                                                                                              |
| red-black tree                                                                                          | O(log n)         | O(log n)                  | O(log n)                  | O(log n)                  | 必須循覽整個序列                                                                                                                                                              |

###

### [\[1.Binary tree\]](https://jenhsuan.gitbook.io/algorithm/algorithms-in-a-nutshell/meet-binary-tree-a-hierarchical-data-structure)

> construct tree, mirror, path sum基本上都可以用recursion的方式完成, 至於是用VLR還是LRV則要看需求是由上到下, 還是由下到上

#### [Level order traversal](https://jenhsuan.gitbook.io/algorithm/notes-of-algorithms/binary-tree-traversal)

* [104.Maximum Depth of Binary Tree (Easy)](https://jenhsuan.gitbook.io/algorithm/leetcode/104.-maximum-depth-of-binary-tree-easy)
* [102. Binary Tree Level Order Traversal (Medium)](https://jenhsuan.gitbook.io/algorithm/leetcode/102.-binary-tree-level-order-traversal-medium)
* [107.Binary Tree Level Order Traversal II (Easy)](https://jenhsuan.gitbook.io/algorithm/leetcode/107.-binary-tree-level-order-traversal-ii-easy)
* [103. Binary Tree Zigzag Level Order Traversal (Medium)](https://jenhsuan.gitbook.io/algorithm/leetcode/103.-binary-tree-zigzag-level-order-traversal)

#### [In-oder traversal](https://jenhsuan.gitbook.io/algorithm/notes-of-algorithms/binary-tree-traversal)

* [94.Binary Tree Inorder Traversal (Medium)](https://jenhsuan.gitbook.io/algorithm/leetcode/94.-binary-tree-inorder-traversal)
* [98.Validate Binary Search Tree (Medium)](https://jenhsuan.gitbook.io/algorithm/leetcode/98.-validate-binary-search-tree-medium)
* [199.Binary Tree Right Side View (Medium)](https://jenhsuan.gitbook.io/algorithm/leetcode/199.-binary-tree-right-side-view-medium)

#### [Post-order traversal](https://jenhsuan.gitbook.io/algorithm/notes-of-algorithms/binary-tree-traversal)

* [110.Balanced Binary Tree (Easy)](https://jenhsuan.gitbook.io/algorithm/leetcode/110.-balanced-binary-tree-easy)
* [145.Binary Tree Postorder Traversal (Hard)](https://jenhsuan.gitbook.io/algorithm/leetcode/145.-binary-tree-postorder-traversal-hard)

#### [Pre-order traversal](https://jenhsuan.gitbook.io/algorithm/notes-of-algorithms/binary-tree-traversal)

* [144.Binary Tree Preorder Traversal (Medium)](https://jenhsuan.gitbook.io/algorithm/leetcode/144.-binary-tree-preorder-traversal-medium)

#### Construct tree

* [654.Maximum Binary Tree](https://jenhsuan.gitbook.io/algorithm/leetcode/654.-maximum-binary-tree)

#### Mirror a binary tree

* [226. Invert Binary Tree](https://jenhsuan.gitbook.io/algorithm/leetcode/226.-invert-binary-tree)

#### Path sum

* [112. Path Sum ](https://jenhsuan.gitbook.io/algorithm/leetcode/untitled)
* [113. Path Sum II](https://jenhsuan.gitbook.io/algorithm/leetcode/113.-path-sum-ii)

#### Lowest Common Ancestor

* [235. Lowest Common Ancestor of a Binary Search Tree](https://jenhsuan.gitbook.io/algorithm/leetcode/236.-lowest-common-ancestor-of-a-binary-tree)

### \[2.Hash table]

> 通過鍵值映射到表中一個位置來訪問記錄以加快查找的速度, 此映射函數就是Hash function, 存放紀錄的數組稱為Hash table

* &#x20;[3. Longest Substring Without Repeating Characters ](https://jenhsuan.gitbook.io/algorithm/leetcode/3.-longest-substring-without-repeating-characters)
* [242. Valid Anagram](https://jenhsuan.gitbook.io/algorithm/leetcode/242.-valid-anagram)&#x20;
* [160. Intersection of Two Linked Lists](https://jenhsuan.gitbook.io/algorithm/leetcode/160.-intersection-of-two-linked-lists)

### [\[3.Stack\]](https://jenhsuan.gitbook.io/algorithm/algorithms-in-a-nutshell/stack)

> 後進先出, 有序容器

* [155. Min Stack](https://jenhsuan.gitbook.io/algorithm/leetcode/155.-min-stack-1)
* 173\. Binary Search Tree Iterator

### [\[4.Queue\]](https://jenhsuan.gitbook.io/algorithm/algorithms-in-a-nutshell/queue)

> 先進先出, 有序容器

* &#x20;[232. Implement Queue using Stacks](https://jenhsuan.gitbook.io/algorithm/leetcode/232.-implement-queue-using-stacks)

### [\[5.Linked list\]](https://jenhsuan.gitbook.io/algorithm/algorithms-in-a-nutshell/linked-list)

#### [Inserting node](https://jenhsuan.gitbook.io/algorithm/notes-of-algorithms/linked-list)

* [147.Insertion Sort List (Medium)](https://jenhsuan.gitbook.io/algorithm/leetcode/147.-insertion-sort-list-medium)

#### Traversal

* [234.Palindrome Linked List (Easy)](https://jenhsuan.gitbook.io/algorithm/leetcode/234.-palindrome-linked-list-easy)

#### Split the list

* [148.Sort List (Medium)](https://jenhsuan.gitbook.io/algorithm/leetcode/148.-sort-list-medium)

#### Delete the node

* [19.Remove Nth Node From End of List (Medium)](https://jenhsuan.gitbook.io/algorithm/leetcode/19.-remove-nth-node-from-end-of-list-medium)
* [203.Remove Linked List Elements](https://jenhsuan.gitbook.io/algorithm/leetcode/203.-remove-linked-list-elements)

#### Reverse list

* [ 206. Reverse Linked List](https://jenhsuan.gitbook.io/algorithm/leetcode/206.-reverse-linked-list)

#### Others

* [23.Merge k Sorted Lists (Hard)](https://jenhsuan.gitbook.io/algorithm/leetcode/23.-merge-k-sorted-lists-hard)
* &#x20;[2. Add Two Numbers](https://jenhsuan.gitbook.io/algorithm/leetcode/2.-add-two-numbers)
* **21. Merge Two Sorted Lists**

###

### \[6.Array]

* 349\. Intersection of Two Arrays
* 442.Find All Duplicates in an Array
* 189\. Rotate Array

###

### \[7.Point]

#### 取址

* 449\. Serialize and Deserialize BST

###

### \[8.Binary search tree]

* [98.Validate Binary Search Tree (Medium)](https://jenhsuan.gitbook.io/algorithm/leetcode/98.-validate-binary-search-tree-medium)

#### Minimum

* &#x20;[230. Kth Smallest Element in a BST](https://jenhsuan.gitbook.io/algorithm/leetcode/230.-kth-smallest-element-in-a-bst)

#### Balance tree

* [110.Balanced Binary Tree (Easy)](https://jenhsuan.gitbook.io/algorithm/leetcode/110.-balanced-binary-tree-easy)
* 109\. Convert Sorted List to Binary Search Tree

#### Find unique BST

* [96. Unique Binary Search Trees](https://jenhsuan.gitbook.io/algorithm/leetcode/96.-unique-binary-search-trees)
* 95\. Unique Binary Search Trees II

#### Search

* &#x20;[700. Search in a Binary Search Tree](https://jenhsuan.gitbook.io/algorithm/leetcode/700.-search-in-a-binary-search-tree)

#### Insert node

* &#x20;[701. Insert into a Binary Search Tree](https://jenhsuan.gitbook.io/algorithm/leetcode/701.-insert-into-a-binary-search-tree)

#### Remove node

* &#x20;450\. Delete Node in a BST

#### Traversal

* 653\. Two Sum IV - Input is a BST
* 449\. Serialize and Deserialize BST
* 783\. Minimum Distance Between BST Nodes

#### Iterator

* 173\. Binary Search Tree Iterator

## 4.Sorting

### \[Overview]

* 最佳, 最糟, 平均 (難以量化): 時間複雜度, 額外空間, 穩定性

| Algorithm                                                                                       | Best       | Average    | Worst      | Space            | Stability | Type     | Properties                                                         |
| ----------------------------------------------------------------------------------------------- | ---------- | ---------- | ---------- | ---------------- | --------- | -------- | ------------------------------------------------------------------ |
| [Insertion sort](https://jenhsuan.gitbook.io/algorithm/algorithms-in-a-nutshell/insertion-sort) | O(n)       | O(n^2)     | O(n^2)     | O(1)             | 穩定        | 換位排序     | <p>1.最佳情形比quick還快(少量元素未排序時)</p><p>2.w出現於元素隨機出現時</p>                |
| [Selection sort](https://jenhsuan.gitbook.io/algorithm/algorithms-in-a-nutshell/selection-sort) | O(n^2)     | O(n^2)     | O(n^2)     | O(1)             | 不穩定       | 換位排序     | 所有排序法最慢的一種, 不會用到前面的結果                                              |
| [Heap sort](https://jenhsuan.gitbook.io/algorithm/algorithms-in-a-nutshell/heap-sort)           | O(n log n) | O(n log n) | O(n log n) | O(1)             | 不穩定       | 換位排序     | 最糟/最佳都是O(n log n)                                                  |
| [Quick sort](https://jenhsuan.gitbook.io/algorithm/algorithms-in-a-nutshell/quick-sort)         | O(n log n) | O(n log n) | O(n^2)     | O(log n) \~ O(n) | 穩定        | 分割排序     | <p>1最糟情形出現在分為"空"與"大"兩個集合時</p><p>2.平均情形比Heap sort快誒, 通常會勝過其他演算法</p> |
| Bucket sort                                                                                     | O(n)       | O(n)       | O(n)       | O(n \* k)        | 穩定        | 非比較排序    |                                                                    |
| Counting sort                                                                                   | O(n + k)   | O(n + k)   | O(n + k)   | O(n + k)         | 穩定        | 非比較排序    |                                                                    |
| [Merge sort](https://jenhsuan.gitbook.io/algorithm/algorithms-in-a-nutshell/merge-sort)         | O(n log n) | O(n log n) | O(n log n) | O(n)             | 穩定        | 需要額外空間排序 | 運用外部資料進行資料轉換最簡單的一個                                                 |

### \[1.換位排序 (Transposition sorting)]

> 與其他元素進行換位將他們移動到正確的位置

#### [1.插入排序 (Insertion sort)](https://jenhsuan.gitbook.io/algorithm/algorithms-in-a-nutshell/insertion-sort)

> 簡述:\
> &#x20;   從最左開始往右滑動, 左邊已滑動過的位置必須是一個sorted list\
> \
> 使用時機/特性: \
> &#x20;    只有少數項目或是大部分項目已排序時適用, 一旦當前的元素比sorted list的最右邊大, 則不在繼續往下比, 移動罩窗

* [147.Insertion Sort List (Medium)](https://jenhsuan.gitbook.io/algorithm/leetcode/147.-insertion-sort-list-medium)
* [283.Move Zeroes](https://jenhsuan.gitbook.io/algorithm/leetcode/283.-move-zeroes)
* [56.Merge Intervals](https://jenhsuan.gitbook.io/algorithm/leetcode/56.-merge-intervals)

#### [2.選擇排序 (Selection sort)](https://jenhsuan.gitbook.io/algorithm/algorithms-in-a-nutshell/selection-sort)

> 簡述:\
> &#x20;   從最左開始往右滑動, 將元素跟左邊剩下的元素逐一比較並找出最小值位置後swap\
> \
> 使用時機/特性:\
> &#x20;   所有排序法最慢的, 每個重複過程沒有利用上一次的結果來做效能的提升&#x20;

#### [3.堆積排序 (Heap sort)](https://jenhsuan.gitbook.io/algorithm/algorithms-in-a-nutshell/heap-sort)

> 簡述:\
> &#x20;   將list轉換成堆積(heap), 迭代呼叫headify處理 \
> \
> 使用時機/特性:\
> &#x20;   在意最糟情形的發生

### \[2.分割排序 (Partition-Based sorting)]

> 分治法是將問題拆成兩個獨立的子問題來解決, 每個子問題大約是原問題的一半, 關鍵點是如何挑選set的中位數 (pivot)

#### [1.快速排序 (Quick sort)](https://jenhsuan.gitbook.io/algorithm/algorithms-in-a-nutshell/quick-sort)

> 描述:\
> &#x20;   1.Partition: 一開始的pivot為最左邊元素, 將l , h交換後, 將h, pivot互換, 返回h\
> &#x20;   2.QuickSort: 呼叫partition, 以及pivot index剖半後的兩個陣列, 再次呼叫Quicksort\
> \
> 使用時機/特性: \
> &#x20;   只對大型陣列使用快速排序, 對小型陣列使用插入排序

* [215.Kth Largest Element in an Array (Medium)](https://jenhsuan.gitbook.io/algorithm/leetcode/215.-kth-largest-element-in-an-array-medium)

### \[3.非比較動作的排序]

> 非比較排序就沒有效能上的限制, 通常可在O(n)完成但缺少靈活性; 比較排序較常應用於實際工作上, 如Mozilla的sort是實作merge sort, webkit是實作selection sort

#### 1.桶子排序 (Bucket sort)

> 簡述\
> &#x20;   桶子是有序容器, 計算所需要桶子的數量後, 將相同區間的成員塞入(排序), 再依序將桶子內的成員倒出即完成\
> 使用時機: \
> &#x20; 1.均勻分布: 輸入資料必須均勻分布於特定範圍, 依據這個分布建立n個桶子均勻分割此輸入範圍\
> &#x20; 2.有序的雜湊函數: 桶子是有序的. 如果 i < j, 插入桶子bi的元素依字典序會小於桶子bj元素\
> 不適用的場合:\
> &#x20; 不適合排序任意的字串, 因為不可能開發一個具有需求字元的雜湊函式

* [347.Top K Frequent Elements](https://jenhsuan.gitbook.io/algorithm/leetcode/347.-top-k-frequent-elements)
* [164. Maximum Gap](https://jenhsuan.gitbook.io/algorithm/leetcode/164.-maximum-gap)

#### 2.計數排序 (Counting sort)

> 最佳, 最差:  複雜度O(n + k), 當k沒有很大時近似於線性\
> 使用時機:  對輸入序列為不超過k, 長度為k 的整數序列可使用\
> 屬於穩定排序法

* [75.Sort Colors (Medium)](https://jenhsuan.gitbook.io/algorithm/leetcode/75.-sort-colors-medium)

### \[4.用額外的儲存空間排序]

> 大部分的排序演算法不需要任何明顯的額外儲存空間

#### [1. 合併排序 (Merge sort)](https://jenhsuan.gitbook.io/algorithm/algorithms-in-a-nutshell/merge-sort)

> 最佳, 最差:  複雜度O(n log n)\
> 空間複雜度: 需要額外的O(n)

* [23.Merge k So  rted Lists (Hard)](https://jenhsuan.gitbook.io/algorithm/leetcode/23.-merge-k-sorted-lists-hard)
* [4.Median of Two Sorted Arrays](https://jenhsuan.gitbook.io/algorithm/leetcode/4.-median-of-two-sorted-arrays)
* 95\. Unique Binary Search Trees II

### \[5.其他]

#### 1.Binary sort

* [148.Sort List (Medium)](https://jenhsuan.gitbook.io/algorithm/leetcode/148.-sort-list-medium)

## 5.Search

### \[Overview]

| Algorithm                  | Best             | Average          | Worst            | Property                                                                                                                          |
| -------------------------- | ---------------- | ---------------- | ---------------- | --------------------------------------------------------------------------------------------------------------------------------- |
| Sequential search          | O(1)             | O(n)             | O(n)             |                                                                                                                                   |
| Binary search              | O(1)             | O(n log n)       | O(log n)         |                                                                                                                                   |
| Hash search                | O(1)             | O(1)             | O(n)             | <p><strong>W:</strong> If too many elements <br>were hashed into the same key: <br>looking inside this key may take O(n) time</p> |
| Binary Search Tree         | O(log n) \~ O(n) | O(log n) \~ O(n) | O(log n) \~ O(n) | **W:** completely unbalance tree                                                                                                  |
| Balance Binary Search Tree | O(log n)         | O(log n)         | O(log n)         |                                                                                                                                   |
| AVL tree                   | O(log n)         | O(log n)         | O(log n)         |                                                                                                                                   |
| B-Tree                     | O(log n)         | O(log n)         | O(log n)         |                                                                                                                                   |
| red-black Tree             | O(log n)         | O(log n)         | O(log n)         |                                                                                                                                   |

### \[1.Binary search]

> 對已排序的合集排序, 切對半直到確定此項目不出現在合集中

* [33. Search in Rotated Sorted Array](https://jenhsuan.gitbook.io/algorithm/leetcode/33.-search-in-rotated-sorted-array) [(Medium)](https://jenhsuan.gitbook.io/algorithm/leetcode/147.-insertion-sort-list-medium)
* [35.Search Insert Position (Easy)](https://jenhsuan.gitbook.io/algorithm/leetcode/35.-search-insert-position-easy)

###

### \[2.Hash search]

> 預先處理 : 計算Ci的雜湊值, hi = hash(Ci), 再將值放入: H\[hi]    -> O(n)\
> 關注點: 雜湊函數的設計以及碰撞的處理\
> 搜尋的步驟: \
> &#x20;    1.計算雜湊值: 運算成本必定在**固定常數**的上界\
> &#x20;    2.存取由雜湊值索引的雜湊表項目: **固定常數**的上界\
> &#x20;    3.在碰撞的存在中找尋特定項目

###

### \[3.Binary search tree]

> 當合集內容變動頻繁時:\
> &#x20;   **二元搜尋**的缺點: 使用已排序陣列會大幅降低演算法的效能\
> &#x20;   **雜湊搜尋**的缺點: 由於不會預先知道要儲存的元素個數, 所以選擇適當大小的雜湊表不是容易的事情\
> 使用時機:\
> &#x20;   1.必須以遞減/遞增順序走訪資料\
> &#x20;   2.資料合集的大小未知, 而且實做必須能夠處理放入記憶體中任何可能的大小內容\
> &#x20;   3.資料合集呈現高度動態, -而且合集的生命週期間有許多插入和刪除動作

### \[4.Balance Binary Search Tree]

> 對平衡的樹而言, 在while迴圈的每次重複過程中, 要搜尋的合集大小會減少一半, 因此有O(log n)的效能

#### AVL Tree

> 1.樹葉節點的高度為0, 非樹葉節點的高度為1, 不存在的子節點的高度為-1\
> 2.任意節點的高度差異為-1, 0, 1\
> 3.每個節點會儲存自己的高度值

## 6.Graph

### \[Overview]

| Algorithm            | Best     | Average  | Worst    | Property |
| -------------------- | -------- | -------- | -------- | -------- |
| Breadth-First Search | O(V + E) | O(V + E) | O(V + E) |          |
| Depth-First Search   | O(V + E) | O(V + E) | O(V + E) |          |

### \[1.Breadth-First Search]

> 保證找出最短路徑

* [127.Word Ladder (Medium)](https://jenhsuan.gitbook.io/algorithm/leetcode/127.-word-ladder-medium)
* [104.Maximum Depth of Binary Tree (Easy)](https://jenhsuan.gitbook.io/algorithm/leetcode/104.-maximum-depth-of-binary-tree-easy)
* [102. Binary Tree Level Order Traversal (Medium)](https://jenhsuan.gitbook.io/algorithm/leetcode/102.-binary-tree-level-order-traversal-medium)
* [107.Binary Tree Level Order Traversal II (Easy)](https://jenhsuan.gitbook.io/algorithm/leetcode/107.-binary-tree-level-order-traversal-ii-easy)
* [103. Binary Tree Zigzag Level Order Traversal (Medium)](https://jenhsuan.gitbook.io/algorithm/leetcode/103.-binary-tree-zigzag-level-order-traversal)<br>

### \[2.Depth-First Search]

> 會盡可能找出較多的路徑, 但不一定是最短路徑

* [337.House Robber III (Medium)](https://jenhsuan.gitbook.io/algorithm/leetcode/337.-house-robber-iii-medium)
* [130.Surrounded Regions (Medium)](https://jenhsuan.gitbook.io/algorithm/leetcode/130.-surrounded-regions-medium)

## 7.General problem

### \[1.Palindrome]

* [9. Palindrome Number (Easy)](https://jenhsuan.gitbook.io/algorithm/leetcode/9.-palindrome-number-easy)
* [409.Longest Palindrome (Easy)](https://jenhsuan.gitbook.io/algorithm/leetcode/409.-longest-palindrome-easy)
* [234.Palindrome Linked List (Easy)](https://jenhsuan.gitbook.io/algorithm/leetcode/234.-palindrome-linked-list-easy)
* **5. Longest Palindromic Substring**

### \[2.Zigzag]

* [6.ZigZag Conversion (Medium)](https://jenhsuan.gitbook.io/algorithm/leetcode/6.zigzag-conversion-medium)

### \[3.Recursion]

#### Back tracking

* [78.Subsets](https://jenhsuan.gitbook.io/algorithm/leetcode/78.-subsets)
* [46.Permutations (Medium)](https://jenhsuan.gitbook.io/algorithm/leetcode/46.-permutations-medium)
* [47.Permutations II (Medium)](https://jenhsuan.gitbook.io/algorithm/leetcode/47.-permutations-ii-medium)
* [654.Maximum Binary Tree](https://jenhsuan.gitbook.io/algorithm/leetcode/654.-maximum-binary-tree)
* 95\. Unique Binary Search Trees II
* 17\. Letter Combinations of a Phone Number
* **22. Generate Parentheses**

### &#x20;\[4.Others]

* [283.Move Zeroes](https://jenhsuan.gitbook.io/algorithm/leetcode/283.-move-zeroes)
* [73.Set Matrix Zeroes (Medium)](https://jenhsuan.gitbook.io/algorithm/leetcode/73.-set-matrix-zeroes-medium)
* [169.Majority Element (Easy)](https://jenhsuan.gitbook.io/algorithm/leetcode/169.-majority-element-easy)
* [1.Two Sum (Easy)](https://jenhsuan.gitbook.io/algorithm/leetcode/1.-two-sum)
* [15. 3Sum](https://jenhsuan.gitbook.io/algorithm/leetcode/15.-3sum)
* &#x20;7\. Reverse Integer&#x20;
* 8\. String to Integer (atoi)
* 11\. Container With Most Water
* 13\. Roman to Integer
* **12. Integer to Roman**
* **14. Longest Common Prefix**

###