CS

Binary Search 二元搜索法 通常一般的二分搜是在解決以下這種問題：如果有一個遞增的函數 \(f\) 定義在區間 \([a, a + n)\) 上，請求出滿足 \(f(s)\ge c\)的最小整數\(s\)。 若用一般的 linear search 從 a 開始搜直到找到滿足條件的 s，那麼複雜度是 \(O(n)\)，而用二元搜索法可以優化時間複雜度變成 \(O(\log n)\)。 想法是對於某個在 \((a, a + n)\) 中的整數 \(k\)，如果 \(f(k − 1) \ge c\)，那麼 \(s < k\)，也就是答案會落在區間 \([a, k)\) 中。 反之，如果 \(f(k − 1) < c\)，那麼 \(s \ge k\)，也就是說你要求的答案會落在 \([k, a + n)\)。 為了讓兩種情況的可能性都盡量低， k 取愈接近 a + n/2 愈好。如此一來，每次候選區間的長度都會縮小一半，因此複雜度為 \(O(\log n)\)。 實務上，這種函數 \(f\) 常常不能直接得出某一點的值 \(f(a)\)（甚至只能確認它和 \(c\) 的大小關係），而需要 \(O(M)\) 的時間來計算。顯然地，這時複雜度是 \(O(M \log n)\)。 1....

前言： 若要對一數組做範圍取值，那麼最快的方法是前綴數組(prefix sum)，可以做到\(O(1)\)的查詢，但若要做單點更新需要\(O(n)\)的時間來維護。 而數組則是做單點更新只需要\(O(1)\)的時間，而要範圍取值則需要\(O(n)\)的查詢時間。 故若是查詢遠大於更新的情境，則適用前綴數組；若更新遠大於查詢的情境，則適用一般數組。 那假如查詢與更新的次數一樣多呢(動態更新與查詢的情境)，這種情況就可以用到此章節要介紹的資料結構，Binary Indexed Tree 了。 此結構可以做到 \(O(n)\) 的初始化，\(\log(n)\) 的更新與 \(\log(n)\) 的查詢。 \( \begin{array}{|c|c|c|}\hline &\textsf{範圍查詢}&\textsf{單點更新}\\\hline \textsf{數組}&O(n)&O(1)\\\hline \textsf{前綴數組}&O(1)&O(n)\\\hline \textsf{BIT}&O(\log n)&O(\log n)\\\hline \end{array} \) 簡介 與線狀樹(Segment Tree)類似，但線狀樹可以看成是 BIT 的擴充版。 BIT 的好處是只需要 n 的數組空間便可以實作，且其指標移動是透過位元運算，計算相當快速，缺點是無法套用到取極大值、極小值的情境。 參考上圖，BIT 利用「部分presum」的特性，來達到平均 \(O\log n\)的查詢與更新的時間，而其實其結構就是 partition 的其中半顆樹。 \(\text{BIT[1]=arr[1]}\) \(\text{BIT[2]=arr[1]+arr[2]}\) \(\text{BIT[3]=arr[3]}\) \(\text{BIT[4]=arr[1]+arr[2]+arr[3]+arr[4]}\) … \(\text{BIT[8]=arr[1]+arr[2]+…+arr[8]}= \text{BIT[4]+BIT[6]+BIT[7]+arr[8]}\) 觀察以上結構， 查詢時，求 [0:n] 的值為把上圖的片段湊起來變成 n 的長度。 如 \(\text{SUM[0:7]=BIT[7]+BIT[6]+BIT[4]}\) 位元表示：\(\text{SUM[0:7]=BIT[1b'111]+BIT[1b'110]+BIT[1b'100]}\) 如 \(\text{SUM[0:11]=BIT[11]+BIT[10]+BIT[8]}\) 位元表示：\(\text{SUM[0:11]=BIT[1b'1011]+BIT[1b'1010]+BIT[1b'1000]}\) 可以發現位元的規律是每次把當前的 LSB(least significant bit) 扣掉。 更新時，需要把包含 n 的片段都更新。(設n=18) 如 \(\text{update(arr[7])=update(BIT[7])+update(BIT[8])+update(BIT[16])}\) 位元表示：\(\text{update(arr[7])=update(BIT[1b'111])+update(BIT[1b'1000])+update(BIT[1b'10000])}\) 如 \(\text{update(arr[11])=update(BIT[11])+update(BIT[12])+update(BIT[16])}\) 位元表示：\(\text{update(arr[7])=update(BIT[1b'1011])+update(BIT[1b'1100])+update(BIT[1b'10000])}\) 可以發現位元的規律是每次把當前的 LSB 加進來。 統整以上規律我們可以寫成以下的模版 將 BIT[0] 設為 dummy，可方便計算。 模板 class BIT { private: vector<int> bit; int lowbit(int a) { return a & (-a); } public: BIT (int n) { bit....

前言： 先前我們在鏈表的單元已經介紹過求鏈表中點的「前後指針」與求有環鏈表的「快慢指針」，這都是雙指針的應用。 在接下來的這個章節，主要會介紹的雙指針應用，與更進階的滑動窗口(sliding window)的應用。 一、Two Pointer in LinkedList 在本文中會學到 LinkedList 的七種技巧： 合併兩個有序鏈表 分解鏈表 合併多個有序鏈表 尋找鏈表的倒數第 k 個節點 尋找鏈表的中點 判斷鏈表是否包含環 判斷兩個鏈表是否相交 1. Merge Two Sorted Lists Leetcode 21. Merge Two Sorted Lists 這一題的小技巧是創建一個 dummy node 依序將兩條鏈表中較小的值接在後面，最後回傳 dummy->next，過程很像 merge sort。 ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { ListNode* dummy = new ListNode(); ListNode* curr = dummy; while (list1 && list2) { if (list1->val <= list2->val) { curr->next = list1; list1 = list1->next; } else { curr->next = list2; list2 = list2->next; } curr = curr->next; } if (list1) curr->next = list1; if (list2) curr->next = list2; return dummy->next; } 二、Two Pointer in Array 三、Sliding Window 回到目錄：[Algo] 演算法筆記 想要複習：[Algo] 3-0....

前言： 在開始練習各種演算法題型時，最先需要養成的是，如何選用「適當」的演算法，題目往往不會只有一種解，但合適的演算法可以如同走捷徑一般，快速且優雅的達到目標。 在實作程式前，更重要的是，寫下一段 pseudo code，試著說明其複雜度，並觀察是否有冗餘的空間可以優化。 在腦海中模擬一遍程式碼之後，最後才是快速的將程式碼實作出來。 在這一章節，我們將練習如何將「想法」轉換成「實作」。並且我們必須熟悉如何計算其時間複雜度。 一、Cheat Table 首先我們需要先瞭解每一種資料結構的各種操作的時間複雜度，以便我們選擇適合的資料結構與演算法。 下面這種表的 Array, Stack, Queue, Linked List, Hash Table, Binary Search Tree 基本上是要背起來的，其餘的遇到再去認識就好。 接下來就輪到練習實作了，排序演算法是個很好的練習，試著把下表中的排序演算法完成，並且計算其時間複雜度吧。 參考題目 Leetcode 912. Sort an Array 二、Sorting Algorithm 0. 測資 這個 file 是我寫的測資，可以拿來測試自己的實作，用法是 #include "agtr.h"，之後用 judge() 函式測試你寫好的 function。 #include <iostream> #include <random> #include <vector> using namespace std; class agtr{ public: static vector<int> exec(int n, int minv, int maxv) { if (minv > maxv) return {}; else if (minv == maxv) return vector<int>(n, minv); vector<int> res; random_device rd; mt19937 mt(rd()); uniform_real_distribution<double> dist(minv, maxv); while (n--) { res....

C#2 Generic 泛型 Nullable 可空值類型 Delegate 委派 Iterator 迭代器 Partial 局部類型 Yield Static Class 靜態類別 Property getter/setter access separate 訪問權限分離 Namespace Alias 空間命名別名 C#3 Linq 及其相關特性