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]

• 198.House Robber (Easy)

• 213.House Robber II (Medium)

• 337.House Robber III (Medium)

• 174.Dungeon Game (Hard)

3.Data Structure

[Overview]

Data structure	Access	Search	Insertion	Deletion	Properties
Binary heap	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
Stack	O(n)	O(n)	O(1)	O(1)	A:必須循覽整個序列 S:必須循覽整個序列 I:push到最上方 D:pop最上方元素
Queue	O(n)	O(n)	O(1)	O(1)	A:必須循覽整個序列 S:必須循覽整個序列 I:從後方enque D:dequeue最前方元素
Single linked list	O(n)	O(n)	O(1)	O(1)	A:必須循覽整個序列 S:必須循覽整個序列
Doubly linked list	O(n)	O(n)	O(1)	O(1)	A:必須循覽整個序列 S:必須循覽整個序列
Array	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)	必須循覽整個序列

[1.Binary tree]

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

Level order traversal

• 104.Maximum Depth of Binary Tree (Easy)

• 102. Binary Tree Level Order Traversal (Medium)

• 107.Binary Tree Level Order Traversal II (Easy)

• 103. Binary Tree Zigzag Level Order Traversal (Medium)

In-oder traversal

• 94.Binary Tree Inorder Traversal (Medium)

• 98.Validate Binary Search Tree (Medium)

• 199.Binary Tree Right Side View (Medium)

Post-order traversal

• 110.Balanced Binary Tree (Easy)

• 145.Binary Tree Postorder Traversal (Hard)

Pre-order traversal

• 144.Binary Tree Preorder Traversal (Medium)

Construct tree

• 654.Maximum Binary Tree

Mirror a binary tree

• 226. Invert Binary Tree

Path sum

• 112. Path Sum

• 113. Path Sum II

Lowest Common Ancestor

• 235. Lowest Common Ancestor of a Binary Search Tree

[2.Hash table]

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

• 3. Longest Substring Without Repeating Characters

• 242. Valid Anagram

• 160. Intersection of Two Linked Lists

[3.Stack]

後進先出, 有序容器

• 155. Min Stack

• 173. Binary Search Tree Iterator

[4.Queue]

先進先出, 有序容器

• 232. Implement Queue using Stacks

[5.Linked list]

Inserting node

• 147.Insertion Sort List (Medium)

Traversal

• 234.Palindrome Linked List (Easy)

Split the list

• 148.Sort List (Medium)

Delete the node

• 19.Remove Nth Node From End of List (Medium)

• 203.Remove Linked List Elements

Reverse list

• 206. Reverse Linked List

Others

• 23.Merge k Sorted Lists (Hard)

• 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)

Minimum

• 230. Kth Smallest Element in a BST

Balance tree

• 110.Balanced Binary Tree (Easy)

• 109. Convert Sorted List to Binary Search Tree

Find unique BST

• 96. Unique Binary Search Trees

• 95. Unique Binary Search Trees II

Search

• 700. Search in a Binary Search Tree

Insert node

• 701. Insert into a Binary Search Tree

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
Insertion sort	O(n)	O(n^2)	O(n^2)	O(1)	穩定	換位排序	1.最佳情形比quick還快(少量元素未排序時) 2.w出現於元素隨機出現時
Selection sort	O(n^2)	O(n^2)	O(n^2)	O(1)	不穩定	換位排序	所有排序法最慢的一種, 不會用到前面的結果
Heap sort	O(n log n)	O(n log n)	O(n log n)	O(1)	不穩定	換位排序	最糟/最佳都是O(n log n)
Quick sort	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)	穩定	非比較排序
Merge sort	O(n log n)	O(n log n)	O(n log n)	O(n)	穩定	需要額外空間排序	運用外部資料進行資料轉換最簡單的一個

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

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

1.插入排序 (Insertion sort)

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

• 147.Insertion Sort List (Medium)

• 283.Move Zeroes

• 56.Merge Intervals

2.選擇排序 (Selection sort)

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

3.堆積排序 (Heap sort)

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

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

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

1.快速排序 (Quick sort)

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

• 215.Kth Largest Element in an Array (Medium)

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

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

1.桶子排序 (Bucket sort)

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

• 347.Top K Frequent Elements

• 164. Maximum Gap

2.計數排序 (Counting sort)

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

• 75.Sort Colors (Medium)

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

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

1. 合併排序 (Merge sort)

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

• 23.Merge k So rted Lists (Hard)

• 4.Median of Two Sorted Arrays

• 95. Unique Binary Search Trees II

[5.其他]

1.Binary sort

• 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)	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]

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

• 33. Search in Rotated Sorted Array (Medium)

• 35.Search Insert Position (Easy)

[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]

保證找出最短路徑

• 127.Word Ladder (Medium)

• 104.Maximum Depth of Binary Tree (Easy)

• 102. Binary Tree Level Order Traversal (Medium)

• 107.Binary Tree Level Order Traversal II (Easy)

• 103. Binary Tree Zigzag Level Order Traversal (Medium)

[2.Depth-First Search]

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

• 337.House Robber III (Medium)

• 130.Surrounded Regions (Medium)

7.General problem

[1.Palindrome]

• 9. Palindrome Number (Easy)

• 409.Longest Palindrome (Easy)

• 234.Palindrome Linked List (Easy)

• 5. Longest Palindromic Substring

[2.Zigzag]

• 6.ZigZag Conversion (Medium)

[3.Recursion]

Back tracking

• 78.Subsets

• 46.Permutations (Medium)

• 47.Permutations II (Medium)

• 654.Maximum Binary Tree

• 95. Unique Binary Search Trees II

• 17. Letter Combinations of a Phone Number

• 22. Generate Parentheses

[4.Others]

• 283.Move Zeroes

• 73.Set Matrix Zeroes (Medium)

• 169.Majority Element (Easy)

• 1.Two Sum (Easy)

• 15. 3Sum

• 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