在前一篇 binary search (1) - 陪你刷題文章中,探討一個基本的 binary search 框架,並指出 binary search 比較常用來解變形題,在 Leetcode 網站上整理出三種 binary search template ,前篇文章中針對 Leetcode #35 的解法即採取下圖中的 Template#2 ,我個人認為 Leetcode 上整理寫的較難理解,千萬不要硬背這三種 template ,應該針對題目要求做對應步驟,在本篇後面就會以實際題目演練如何應用 template 。
分類: Leetcode
Trie 字典樹 – 陪你刷題
Trie 是一種樹狀結構,可以用來在大量字串中快速搜尋某個字串。雖然這個問題也可以用 hash table 來解決,但在以下情況下,Trie 有其獨特的優勢:
- 找出每個有特定前綴的字串。
- 按照字典順序列出所有字串。
Binary Search (1) – 陪你刷題
Binary search 是一種在有序陣列做搜尋的演算法,在最壞的狀況下,其時間複雜度為 O (log n)
對數時間,相當高效。
Binary search 框架
以下是 binary search 的框架,但只適用於有序且不含重複元素的 Array :
int bsearch(vector<int>& a, int value) {
int low = 0;
int high = a.size()-1;
while (low <= high) {
int mid = low + ((high-low)>>1);
if (a[mid] == value) {
return mid;
} else if (a[mid] < value) {
low = mid + 1;
} else if (a[mid] > value) {
high = mid - 1;
}
}
return -1;
}