Leetcode
The records of self practices for Leetcode challenges
1.Performance
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]
3.Data Structure
[Overview]
Data structure | Access | Search | Insertion | Deletion | Properties |
O(1) | O(log n) | O(log n) | O(log n) | A:直接索引 S: log n層 I:插到最後, sift up D:移除root, 將最大值移到root後sift down root | |
Hash table | NA | O(1) ~ O(n) | O(1) ~ O(n) | O(1) ~ O(n) | A:無法索引 S: 必須用Key索引 I: 計算hash值後插入 D:計算hash值後移除 W: collision |
O(n) | O(n) | O(1) | O(1) | A:必須循覽整個序列 S:必須循覽整個序列 I:push到最上方 D:pop最上方元素 | |
O(n) | O(n) | O(1) | O(1) | A:必須循覽整個序列 S:必須循覽整個序列 I:從後方enque D:dequeue最前方元素 | |
O(n) | O(n) | O(1) | O(1) | A:必須循覽整個序列 S:必須循覽整個序列 | |
O(n) | O(n) | O(1) | O(1) | A:必須循覽整個序列 S:必須循覽整個序列 | |
O(1) | O(n) | O(n) | O(n) | A:直接索引 S, I, D:必須循覽整個序列 | |
Binary Search Tree | O(log n) ~ O(n) | O(log n) ~ O(n) | O(log n) ~ O(n) | O(log n) ~ O(n) | 必須循覽整個序列 W: unbalance |
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) | 必須循覽整個序列 |
construct tree, mirror, path sum基本上都可以用recursion的方式完成, 至於是用VLR還是LRV則要看需求是由上到下, 還是由下到上
Construct tree
Mirror a binary tree
Path sum
Lowest Common Ancestor
[2.Hash table]
通過鍵值映射到表中一個位置來訪問記錄以加快查找的速度, 此映射函數就是Hash function, 存放紀錄的數組稱為Hash table
後進先出, 有序容器
173. Binary Search Tree Iterator
先進先出, 有序容器
Traversal
Split the list
Delete the node
Reverse list
Others
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]
Minimum
Balance tree
109. Convert Sorted List to Binary Search Tree
Find unique BST
95. Unique Binary Search Trees II
Search
Insert node
Remove node
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 |
O(n) | O(n^2) | O(n^2) | O(1) | 穩定 | 換位排序 | 1.最佳情形比quick還快(少量元素未排序時) 2.w出現於元素隨機出現時 | |
O(n^2) | O(n^2) | O(n^2) | O(1) | 不穩定 | 換位排序 | 所有排序法最慢的一種, 不會用到前面的結果 | |
O(n log n) | O(n log n) | O(n log n) | O(1) | 不穩定 | 換位排序 | 最糟/最佳都是O(n log n) | |
O(n log n) | O(n log n) | O(n^2) | O(log n) ~ O(n) | 穩定 | 分割排序 | 1最糟情形出現在分為"空"與"大"兩個集合時 2.平均情形比Heap sort快誒, 通常會勝過其他演算法 | |
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) | 穩定 | 非比較排序 | |
O(n log n) | O(n log n) | O(n log n) | O(n) | 穩定 | 需要額外空間排序 | 運用外部資料進行資料轉換最簡單的一個 |
[1.換位排序 (Transposition sorting)]
與其他元素進行換位將他們移動到正確的位置
簡述: 從最左開始往右滑動, 左邊已滑動過的位置必須是一個sorted list 使用時機/特性: 只有少數項目或是大部分項目已排序時適用, 一旦當前的元素比sorted list的最右邊大, 則不在繼續往下比, 移動罩窗
簡述: 從最左開始往右滑動, 將元素跟左邊剩下的元素逐一比較並找出最小值位置後swap 使用時機/特性: 所有排序法最慢的, 每個重複過程沒有利用上一次的結果來做效能的提升
簡述: 將list轉換成堆積(heap), 迭代呼叫headify處理 使用時機/特性: 在意最糟情形的發生
[2.分割排序 (Partition-Based sorting)]
分治法是將問題拆成兩個獨立的子問題來解決, 每個子問題大約是原問題的一半, 關鍵點是如何挑選set的中位數 (pivot)
描述: 1.Partition: 一開始的pivot為最左邊元素, 將l , h交換後, 將h, pivot互換, 返回h 2.QuickSort: 呼叫partition, 以及pivot index剖半後的兩個陣列, 再次呼叫Quicksort 使用時機/特性: 只對大型陣列使用快速排序, 對小型陣列使用插入排序
[3.非比較動作的排序]
非比較排序就沒有效能上的限制, 通常可在O(n)完成但缺少靈活性; 比較排序較常應用於實際工作上, 如Mozilla的sort是實作merge sort, webkit是實作selection sort
1.桶子排序 (Bucket sort)
簡述 桶子是有序容器, 計算所需要桶子的數量後, 將相同區間的成員塞入(排序), 再依序將桶子內的成員倒出即完成 使用時機: 1.均勻分布: 輸入資料必須均勻分布於特定範圍, 依據這個分布建立n個桶子均勻分割此輸入範圍 2.有序的雜湊函數: 桶子是有序的. 如果 i < j, 插入桶子bi的元素依字典序會小於桶子bj元素 不適用的場合: 不適合排序任意的字串, 因為不可能開發一個具有需求字元的雜湊函式
2.計數排序 (Counting sort)
最佳, 最差: 複雜度O(n + k), 當k沒有很大時近似於線性 使用時機: 對輸入序列為不超過k, 長度為k 的整數序列可使用 屬於穩定排序法
[4.用額外的儲存空間排序]
大部分的排序演算法不需要任何明顯的額外儲存空間
最佳, 最差: 複雜度O(n log n) 空間複雜度: 需要額外的O(n)
95. Unique Binary Search Trees II
[5.其他]
1.Binary sort
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) | W: If too many elements were hashed into the same key: looking inside this key may take O(n) time |
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]
對已排序的合集排序, 切對半直到確定此項目不出現在合集中
[2.Hash search]
預先處理 : 計算Ci的雜湊值, hi = hash(Ci), 再將值放入: H[hi] -> O(n) 關注點: 雜湊函數的設計以及碰撞的處理 搜尋的步驟: 1.計算雜湊值: 運算成本必定在固定常數的上界 2.存取由雜湊值索引的雜湊表項目: 固定常數的上界 3.在碰撞的存在中找尋特定項目
[3.Binary search tree]
當合集內容變動頻繁時: 二元搜尋的缺點: 使用已排序陣列會大幅降低演算法的效能 雜湊搜尋的缺點: 由於不會預先知道要儲存的元素個數, 所以選擇適當大小的雜湊表不是容易的事情 使用時機: 1.必須以遞減/遞增順序走訪資料 2.資料合集的大小未知, 而且實做必須能夠處理放入記憶體中任何可能的大小內容 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]
保證找出最短路徑
[2.Depth-First Search]
會盡可能找出較多的路徑, 但不一定是最短路徑
7.General problem
[1.Palindrome]
5. Longest Palindromic Substring
[2.Zigzag]
[3.Recursion]
Back tracking
95. Unique Binary Search Trees II
17. Letter Combinations of a Phone Number
22. Generate Parentheses
[4.Others]
7. Reverse Integer
8. String to Integer (atoi)
11. Container With Most Water
13. Roman to Integer
12. Integer to Roman
14. Longest Common Prefix
Last updated