Leetcode, Codility , GeekforGeeks algorithms exercises written in Golang.
leetcode Content
| No. | Title | Solution | Difficulty | Time | Space | Topic |
|---|---|---|---|---|---|---|
| 0001 | Two Sum | Go | Easy | O(n) | O(n) | Array |
| 0003 | Longest Substring Without Repeating Characters | Go | Medium | O(n) | O(1) | Array |
| 0015 | 3 Sum | Go | Medium | O(n^2) | O(n) | Array |
| 0027 | Remove Element | Go | Easy | O(n) | O(1) | Array |
| 0035 | Search Insert Position | Go | Easy | O(n), O(logn) | O(1) | Array |
| 0059 | Spiral Matrix II | Go | Medium | O(n) | O(n^2) | Array |
| 0088 | Merge Sorted Array | Go | Easy | O(n) | O(1) | Array |
| No. | Topic | Title | Solution | Difficulty | TimeComplexity | SpaceComplexity |
|---|---|---|---|---|---|---|
| 0094 | Stack | Binary Tree Inorder Traversal | Go | Medium | O(n)) | O(1) |
| No. | Topic | Title | Solution | Difficulty | TimeComplexity | SpaceComplexity |
|---|---|---|---|---|---|---|
| 0141 | Linked List | Linked List Cycle | Go | Easy | O(n) | O(1) |
| 0203 | Linked List | Remove Linked List Elements | Go | Easy | O(n) | O(1) |
| No. | Topic | Title | Solution | Difficulty | TimeComplexity | SpaceComplexity |
|---|---|---|---|---|---|---|
| 0075 | Sort | Sort Colors | Go | Medium | O(n)) | O(1) |
DFS. 解決一個回溯問題, 實際上就是一個決策數的遍歷過程. 算是一個暴力的窮舉算法
- 路徑：也就是已經做出的選擇。
- 選擇列表：也就是你當前可以做的選擇。
- 結束條件：也就是到達決策樹底層，無法再做選擇的條件。
result = []
def backtrack(路徑, 選擇列表):
if 滿足結束條件:
result.add(路徑)
return
for 選擇 in 選擇列表:
做選擇(前序)
backtrack(路徑, 選擇列表)
撤銷選擇(後序)| No. | Topic | Title | Solution | Difficulty | TimeComplexity | SpaceComplexity |
|---|---|---|---|---|---|---|
| 0046 | Backtracking | Permutations (排列) | Go | Medium | O(n) | O(n) |
動態規劃問題的一般形式就是求最值, 最長遞增子序列, 最小編輯距離等. 核心問題是窮舉
- 重疊子問題
- memory table
- DP table
- 最優子結構
- 狀態轉移方程式
- 這問題的 base case (最簡單情況) 是什麼?
- 這問題有什麼狀態
- 對於每個狀態, 可以做出什麼選擇, 使得狀態發生改變
- 如何定義 dp 數組/函數的含義來表現狀態和選擇?
# 初始化 base case
dp[0][0][...] = base
# 進行狀態轉移
for 狀態1 in 狀態1的所有取值：
for 狀態2 in 狀態2的所有取值：
for ...
dp[狀態1][狀態2][...] = 求最值(選擇1，選擇2...)| No. | Topic | Title | Solution | Difficulty | TimeComplexity | SpaceComplexity |
|---|---|---|---|---|---|---|
| 0053 | Dynamic Programming | Maximum Subarray | Go | Easy | O(n) | O(n) |
| 0322 | Dynamic Programming | Coin Change | Go | Medium | O(nm) | O(n) |
| 0509 | Dynamic Programming | Fibonacci Number | Go | Easy | 很多解法 | 很多解法 |
| No. | Topic | Title | Solution | Difficulty | TimeComplexity | SpaceComplexity |
|---|---|---|---|---|---|---|
| 0209 | Sliding Window | Minimum Size Subarray Sum | Go | Medium | O(n^2), O(n), O(nlog n) | O(1), O(1), O(n) |
| No. | Topic | Title | Solution | Difficulty | TimeComplexity | SpaceComplexity |
|---|---|---|---|---|---|---|
| 0344 | Two Pointers | Reverse String | Go | Easy | O(n) | O(1) |
| No. | Topic | Title | Solution | Difficulty | TimeComplexity | SpaceComplexity |
|---|---|---|---|---|---|---|
| 0693 | Bit Manipulation | Binary Number with Alternating Bits | Go | Easy | O(n), O(1) | O(1) |
| No. | Topic | Title | Solution | Difficulty | TimeComplexity | SpaceComplexity |
|---|---|---|---|---|---|---|
| 0721 | Union Find | Accounts Merge | Go | Easy | O(n), O(n log n) | O(n), O(n) |
DFS 算法可以被認為是回溯算法, BFS算法都是用Queue這種數據結構, 每次將一個截短周圍的所有節點加入Queue. BFS 找到的路徑一定是最短的, 但是代價是空間複雜度比DFS大 BFS vs DFS
// 計算從起點 start 到 終點 target 的最點距離
int BFS(Node start, Node targe){
Queue<Node> q; // 核心數據結構
Set<Node> visited; // 避免走回頭路
q.offer(start); // 將起點加入 Queue
visited.add(start);
int step = 0; // 紀錄擴散的步數
while(q not empty) {
int sz = q.size();
// 當前 Queue 中的所有節點向四周擴散
for (int i = 0 ; i < sz; i++) {
Node cur = q.poll();
// 這裡判斷是否到達終點
if (cur is target) {
return step;
}
// 將cur 的相鄰節點加入 Queue
for (Node x : cur.adj()) {
if (x not in visited) {
q.offer(x);
visited.add(x);
}
}
}
// 在這裡更新步數
step++
}
}| No. | Topic | Title | Solution | Difficulty | TimeComplexity | SpaceComplexity |
|---|---|---|---|---|---|---|
| 0310 | Breadth First Search | Minimum Height Trees | Go | Medium |
GeeksforGeeks Content
| Topic | Title | No. | Solution | Difficulty | TimeComplexity | SpaceComplexity |
|---|---|---|---|---|---|---|
| Sorting | Find Minimum Difference Between Any Two Elements | 0031 | Go | Basic | O(n^2), O(n log n) | O(n), O(n) |
Codility Content
| Topic | Title | Solution | Difficulty | TimeComplexity | SpaceComplexity | |
|---|---|---|---|---|---|---|
| Lesson 1 |
Iterations |
Binary Gap |
Go |
Painless | O(log n) | O(1) |
| Lesson 2 |
Array |
Cyclic Rotation |
Go |
Painless | O(1) | O(1) |
|
Odd Occurrences In Array |
Go |
Painless | O(n), O(n) | O(n), O(1) | ||
| Lesson 3 |
Time Complexity |
Frog Jmp |
Go |
Painless | O(1) | O(1) |
|
Perm Missing Elem |
Go |
Painless | O(n) | O(1) | ||
|
Tape Equilibrium |
Go |
Painless | O(n) | O(n) | ||
| Lesson 4 |
Counting Elements |
Frog River One |
Go |
Painless | O(n) | O(n) |
|
Max Counters |
Go |
Respectable | O(n+m) | O(n) | ||
|
Missing Integer |
Go |
Respectable | O(n) | O(n) | ||
|
Perm Check |
Go |
Painless | O(n) | O(n) | ||
| Lesson 5 |
Prefix Sums |
Count Div |
Go |
Respectable | O(1) | O(1) |
|
Genomic Range Query |
Go |
Respectable | O(n+m) | O(n) | ||
|
MinAvg Two Slice |
Go |
Respectable | O(n) | O(n) | ||
|
Passing Cars |
Go |
Painless | O(n) | O(1) | ||
| Lesson 6 |
Sorting |
Distinct |
Go |
Painless | O(nlogn) | O(n) |
|
Max Product of Three |
Go |
Painless | O(nlogn) | O(1) | ||
|
Number Of Disc Intersections |
Go |
Respectable | O(nlogn) | O(n) | ||
|
Triangle |
Go |
Painless | O(nlogn) | O(n) | ||
| Lesson 7 |
Stacks and Queues |
Brackets |
Go |
Painless | O(n) | O(n) |
|
Fish |
Go |
Painless | O(n) | O(n) | ||
|
Nesting |
Go |
Painless | O(n) | O(1) | ||
|
Stone Wall |
Go |
Painless | O(n) | O(n) | ||
| Lesson 8 |
Leader |
Dominator |
Go |
Painless | O(n) | O(1) |
|
EquiLeader |
Go |
Painless | O(n) | O(n) | ||
| Lesson 9 |
Maximum slice problem |
Max Profit |
Go |
Painless | O(n) | O(1) |
|
Max Slice Sum |
Go |
Painless | O(n) | O(n) | ||
|
Max Double Slice Sum |
Go |
Respectable | O(n) | O(n) | ||
| Lesson 10 |
Prime and composite numbers |
Count Factors |
Go |
Painless | O(sqrt(n)) | O(1) |
|
Flags |
Go |
Respectable | O(n) | O(n) | ||
|
MinPerimeterRectangle |
Go |
Painless | O(sqrt(n))) | O(1) | ||
|
Peaks |
Go |
Respectable | O( n*log( log(n) )) | O(n) | ||
| Lesson 11 |
Sieve of Eratosthenes (質數篩) |
Count Non Divisible |
Go |
Respectable | O(N * log(N)) | O(n) |
|
Count Semiprimes |
Go |
Respectable | O(N*log(log(N))+M) | O(N+M) | ||
| Lesson 12 |
Euclidean algorithm (輾轉相除法 or 歐幾里得算法) |
Chocolates By Numbers |
Go |
Painless | O(log(N + M)) | O(1) |
|
Common Prime Divisors |
Go |
Respectable | O(Z * log(max(A) + max(B))**2) | O(1) | ||
| Lesson 13 |
Fibonacci numbers |
FibFrog |
Go |
Respectable | O(N * log(N)) | O(N) |
|
Ladder |
|
Respectable | ||||
| Lesson 14 |
Binary search algorithm |
MinMaxDivision |
|
Respectable | ||
|
NailingPlanks |
|
Respectable | ||||
| Lesson 15 |
Caterpillar method |
AbsDistinct |
|
Painless | ||
|
CountDistinctSlices |
|
Painless | ||||
|
CountTriangles |
|
Painless | ||||
|
MinAbsSumOfTwo |
|
Respectable | ||||
| Lesson 16 |
Greedy algorithms |
MaxNonoverlappingSegments |
|
Painless | ||
|
TieRopes |
|
Painless | ||||
| Lesson 17 |
Dynamic programming |
MinAbsSum |
|
Ambitious | ||
|
NumberSolitaire |
|
Respectable | ||||