8 篇有 "algorithm" 標籤的文章
Binary Search 二元搜尋法
在一個已排序的陣列中，可用 binary search 演算法快速找到你要的數字。Binary search 概念雖然簡單，但是實作上卻有許多細節需要注意，要加一減一？小於還是小於等於？都需要非常小心。 Binary Search…
Read more →二元堆積 (Binary Heap)、最小堆積 (Min Heap) 與最大堆積 (Max Heap)
Binary Heap (二元堆積) 是一種常見的資料結構，適合需要取最大最小值的場合，也適合用來解決 top-k 問題，同時也常被用來實作 priortity queue (優先權佇列)。在 Dijkstra 演算法中，堆積也扮演了重要的角色。Binary Heap…
Read more →Quick Sort 演算法原理與實作
Quick sort 快速排序演算法是一種 divide and conquer 的陣列排序方法，其過程如下：先從 array 中選出一個元素當基準 (pivot)，然後讓 pivot 左邊的元素都小於等於 pivot，pivot 右邊的元素都大於 pivot…
Read more →三種 Iterative Binary Tree Traversal 的方法 (Inorder, Preorder, Postorder)
遍歷二元樹 (Binary Tree Traversal) 的順序有三種，分別是前序 (preorder), 中序 (inorder) 和後序 (postorder)。遍歷二元樹實作又可以分為遞迴 (recursive) 和迭代 (iterative…
Read more →Caterpillar Method
令 A = [a0, a1, …, an-1], ai > 0，要如何判斷是否存在一組 (p, q)，其中 p <= q，使得 sum(ap, ap+1, … aq) = s？我們可以用下面介紹的Caterpillar Method。 目錄 Caterpillar Method…
Read more →最大子數列問題 (Maximum Subarray Problem) 及 Kadane's Algorithm
給定 A = [a0, a1, …, an-1]，如何使得 slice 的和 sum(A[p], A[p+1], …, A[q]) 有最大值 (slice長度可以為0) ？有個知名的 Kadane’s Algorithm 可以解決這個問題。 目錄 Kadane’s…
Read more →Min Abs Sum
給定A = [a0, a1, …, an-1]，如何找到一組S = [s0, s1, … sn-1], sj ∈ {-1, 1}, 使得abs(sum(ai * si))有最小值？關鍵在於對於 A 中的每個元素 a 能夠產生的 sum…
Read more →Sum of subarray 的實用解題技巧
當遇到 sum of subarray 相關的問題時，有個很實用的解題技巧：所有的 sum of subarray 都可以用 Si - Sj 組出來，其中 Si = a0 + a1 + … + ai。 目錄 問題: 0 mod n Sum Subset Problem…
Read more →