Leetcode
The records of self practices for Leetcode challenges
Last updated
The records of self practices for Leetcode challenges
Last updated
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)
分為解析 (真正處理問題的程序)以及以及遞迴, 如果解析需要O(n)時間, 則每次都分為兩半則總共需要O(n log n)時間
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則要看需求是由上到下, 還是由下到上
通過鍵值映射到表中一個位置來訪問記錄以加快查找的速度, 此映射函數就是Hash function, 存放紀錄的數組稱為Hash table
後進先出, 有序容器
173. Binary Search Tree Iterator
先進先出, 有序容器
21. Merge Two Sorted Lists
349. Intersection of Two Arrays
442.Find All Duplicates in an Array
189. Rotate Array
449. Serialize and Deserialize BST
109. Convert Sorted List to Binary Search Tree
95. Unique Binary Search Trees II
450. Delete Node in a BST
653. Two Sum IV - Input is a BST
449. Serialize and Deserialize BST
783. Minimum Distance Between BST Nodes
173. Binary Search Tree Iterator
最佳, 最糟, 平均 (難以量化): 時間複雜度, 額外空間, 穩定性
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)
穩定
需要額外空間排序
運用外部資料進行資料轉換最簡單的一個
與其他元素進行換位將他們移動到正確的位置
簡述: 從最左開始往右滑動, 左邊已滑動過的位置必須是一個sorted list 使用時機/特性: 只有少數項目或是大部分項目已排序時適用, 一旦當前的元素比sorted list的最右邊大, 則不在繼續往下比, 移動罩窗
簡述: 從最左開始往右滑動, 將元素跟左邊剩下的元素逐一比較並找出最小值位置後swap 使用時機/特性: 所有排序法最慢的, 每個重複過程沒有利用上一次的結果來做效能的提升
簡述: 將list轉換成堆積(heap), 迭代呼叫headify處理 使用時機/特性: 在意最糟情形的發生
分治法是將問題拆成兩個獨立的子問題來解決, 每個子問題大約是原問題的一半, 關鍵點是如何挑選set的中位數 (pivot)
描述: 1.Partition: 一開始的pivot為最左邊元素, 將l , h交換後, 將h, pivot互換, 返回h 2.QuickSort: 呼叫partition, 以及pivot index剖半後的兩個陣列, 再次呼叫Quicksort 使用時機/特性: 只對大型陣列使用快速排序, 對小型陣列使用插入排序
非比較排序就沒有效能上的限制, 通常可在O(n)完成但缺少靈活性; 比較排序較常應用於實際工作上, 如Mozilla的sort是實作merge sort, webkit是實作selection sort
簡述 桶子是有序容器, 計算所需要桶子的數量後, 將相同區間的成員塞入(排序), 再依序將桶子內的成員倒出即完成 使用時機: 1.均勻分布: 輸入資料必須均勻分布於特定範圍, 依據這個分布建立n個桶子均勻分割此輸入範圍 2.有序的雜湊函數: 桶子是有序的. 如果 i < j, 插入桶子bi的元素依字典序會小於桶子bj元素 不適用的場合: 不適合排序任意的字串, 因為不可能開發一個具有需求字元的雜湊函式
最佳, 最差: 複雜度O(n + k), 當k沒有很大時近似於線性 使用時機: 對輸入序列為不超過k, 長度為k 的整數序列可使用 屬於穩定排序法
大部分的排序演算法不需要任何明顯的額外儲存空間
最佳, 最差: 複雜度O(n log n) 空間複雜度: 需要額外的O(n)
95. Unique Binary Search Trees II
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)
對已排序的合集排序, 切對半直到確定此項目不出現在合集中
預先處理 : 計算Ci的雜湊值, hi = hash(Ci), 再將值放入: H[hi] -> O(n) 關注點: 雜湊函數的設計以及碰撞的處理 搜尋的步驟: 1.計算雜湊值: 運算成本必定在固定常數的上界 2.存取由雜湊值索引的雜湊表項目: 固定常數的上界 3.在碰撞的存在中找尋特定項目
當合集內容變動頻繁時: 二元搜尋的缺點: 使用已排序陣列會大幅降低演算法的效能 雜湊搜尋的缺點: 由於不會預先知道要儲存的元素個數, 所以選擇適當大小的雜湊表不是容易的事情 使用時機: 1.必須以遞減/遞增順序走訪資料 2.資料合集的大小未知, 而且實做必須能夠處理放入記憶體中任何可能的大小內容 3.資料合集呈現高度動態, -而且合集的生命週期間有許多插入和刪除動作
對平衡的樹而言, 在while迴圈的每次重複過程中, 要搜尋的合集大小會減少一半, 因此有O(log n)的效能
1.樹葉節點的高度為0, 非樹葉節點的高度為1, 不存在的子節點的高度為-1 2.任意節點的高度差異為-1, 0, 1 3.每個節點會儲存自己的高度值
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)
保證找出最短路徑
會盡可能找出較多的路徑, 但不一定是最短路徑
5. Longest Palindromic Substring
95. Unique Binary Search Trees II
17. Letter Combinations of a Phone Number
22. Generate Parentheses
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