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. 三元搜 利用二分搜這種「縮短候選人長度」的想法，我們可以找出滿足特定性質的函數的最小值，這種技巧稱為三分搜。 三分搜處理的問題如下：有一個在 \([a, a + n)\) 中先嚴格遞減再嚴格遞增的函數 \(f\)，請求出 \(f\) 在 \([a, a + n)\) 的最小值。取在 \([a, a + n)\) 中的兩個整數 \(x < y\)。如果 \(f(x) < f(y)\)，那麼最小值一定落在 \([a, y)\)。如果 \(f(x) > f(y)\)，那麼最小值一定落在 \((x, a + n)\)。如果 \(f(x) = f(y)\)，那麼最小值一定落在 \((x, y)\)。為了讓候選區間每次都會縮短一定的比例，通常都取 x 跟 y 為區間的三等分點（取中間一點的話常數會變小）。複雜度仍然是 \(O(\log n)\)。 2. 對答案二分搜 有許多問題都喜歡叫你求「滿足條件的最小值」這種東西。如果這個問題滿足「單調 性」，那或許可以考慮對答案二分搜。 什麼是「單調性」呢？考慮一個函數 P，如果 s 滿足條件，那麼 P(s) = 1，反之則為 0。如果 P 有單調性，我們就說這個問題有單調性。這樣的好處是，我們可以直接用前面的方法二分搜出要求的 s。如果計算 P 的複雜度並不大時，這樣的方法可以有非常的表現效率。在你沒辦法快速求出 s 而只能快速確認一個 s 是否符合條件時，這是一個非常好的方法。 例題：Leetcode875. Koko Eating Bananas 以此題而言， canFinish 就是一個具備單調性的函式，符合我們對答案作二分搜的條件。 int minEatingSpeed(vector<int>& piles, int h) { int max = *max_element(piles.begin(), piles.end()); if (piles.size() == h) return max; int left = 1, right = max + 1; while (left < right){ int mid = left + (right-left)/2; if (canFinish(piles, mid, h)){ right = mid; } else { left = mid + 1; } } return left; } bool canFinish(vector<int> piles, int speed, int h){ int time = 0; for (int n : piles){ time += n/speed + ((n % speed > 0) ? 1 : 0); } return time <= h; } 回到目錄：[Algo] 演算法筆記 想要複習：[Algo] 3-1. Two Pointer 接著閱讀：[Algo] 3-3. Monotonic Stack

前言： 若要對一數組做範圍取值，那麼最快的方法是前綴數組(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.assign(n+1, 0); } void add(int idx, int diff) { idx++; int n = bit.size(); while (idx < n) { bit[idx] += diff; idx += lowbit(idx); } } int query(int idx) { int sum = 0; idx++; while (idx > 0) { sum += bit[idx]; idx -= lowbit(idx); } return sum; } } 回目錄 Catalog ...

前言： 先前我們在鏈表的單元已經介紹過求鏈表中點的「前後指針」與求有環鏈表的「快慢指針」，這都是雙指針的應用。 在接下來的這個章節，主要會介紹的雙指針應用，與更進階的滑動窗口(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. Sorting 接著閱讀：[Algo] 3-2. Binary Search

前言： 在開始練習各種演算法題型時，最先需要養成的是，如何選用「適當」的演算法，題目往往不會只有一種解，但合適的演算法可以如同走捷徑一般，快速且優雅的達到目標。 在實作程式前，更重要的是，寫下一段 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.push_back(dist(mt)); } return res; } static vector<int> exec(int n) { return exec(n, 0, 10); } static vector<int> exec() { return exec(10); } static void print(vector<int>& nums) { cout << "["; for_each(nums.begin(), nums.end()-1, [](int x) { cout << x << ","; }); cout << *(nums.end()-1) << "]"; } static bool check(vector<int>& nums, vector<int> copy) { sort(copy.begin(), copy.end()); for (int i = 0; i < nums.size(); i++) { if (nums[i] != copy[i]) return false; } return true; } static void judge(void (*func)(vector<int>&)) { int n = 10; bool test = true; int cnt = 0; while (n--) { auto nums = exec(); auto copy = vector<int>(nums.begin(), nums.end()); print(nums); (*func)(nums); cout << "->"; print(nums); int result = check(nums, copy); cout << "(" << (result ? "Pass" : "Fail") << ")" << endl; if (result) cnt++; test &= result; } if (test) { cout << "Pass! (10/10)" << endl; } else { cout << "Fail! (" << cnt << "/10)" << endl; } } }; 以下為測試的方式 # include "agtr.h" void sort(vector<int>& nums) {...} // 你的實作 int main() { agtr::judge(sort); // 用這個函式測試你的實作 return 0; } 1. Bubble Sort void sort(vector<int>& nums) { int n = nums.size(); for (int i = n-1; i > 0; i--) { for (int j = 0; j < i; j++) { if (nums[j] > nums[j+1]) swap(nums[j], nums[j+1]); } } } 2. Selection SOrt void sort(vector<int>& nums) { int n = nums.size(); for (int i = 0; i < n-1; i++) { int p = i; for (int j = i+1; j < n; j++) { if (nums[j] < nums[p]) p = j; } swap(nums[p], nums[i]); } } 3. Insertion Sort void sort(vector<int>& nums){ int n = nums.size(); for (int i = 1; i < n; i++) { int j = i-1; int curr = nums[i]; for (; j >= 0; j--) { if (nums[j] <= curr) { break; } nums[j+1] = nums[j]; } nums[j+1] = curr; } } 4. Heap Sort void heapify(vector<int>& nums, int i) { int left = 2*i+1; int right = 2*i+2; int p = i; int n = nums.size(); if (left < n && nums[left] < nums[p]) p = left; if (right < n && nums[right] < nums[p]) p = right; if (p != i) { swap(nums[i], nums[p]); heapify(nums, p); } } void sort(vector<int>& nums) { vector<int> vec(nums.begin(), nums.end()); int n = vec.size(); int parent = (n-1)/2; for (int i = parent; i >= 0; i--) { heapify(vec, i); } for (int i = 0; i < n; i++) { nums[i] = vec[0]; vec[0] = vec.back(); vec.pop_back(); heapify(vec, 0); } } 5. Tree Sort class TreeNode { private: TreeNode* left, *right; int val; TreeNode* insert(TreeNode* root, int val) { if (!root) { root = new TreeNode(val); return root; } if (val < root->val) { root->left = insert(root->left, val); } else { root->right = insert(root->right, val); } return root; } void dfs(TreeNode* root, vector<int>& nums) { if (!root) return; dfs(root->left, nums); nums.push_back(root->val); dfs(root->right, nums); } public: TreeNode() {} TreeNode(int val) : val(val) {} TreeNode(int val, TreeNode* left, TreeNode* right) : val(val), left(left), right(right) {} void insert(int val) { insert(this, val); } vector<int> getArray() { vector<int> nums; dfs(this, nums); return nums; } }; void sort(vector<int>& nums) { TreeNode* root = new TreeNode(nums[0]); for (int i = 1; i < nums.size(); i++) { root->insert(nums[i]); } nums = root->getArray(); } 6. Merge Sort void merge(vector<int>& nums, int left, int mid, int right) { int i = left, j = mid + 1; vector<int> tmp; while (i <= mid && j <= right) { if (nums[i] < nums[j]) tmp.push_back(nums[i++]); else tmp.push_back(nums[j++]); } while (i <= mid) tmp.push_back(nums[i++]); while (j <= right) tmp.push_back(nums[j++]); for (i = left; i <= right; i++) { nums[i] = tmp[i-left]; } } void sort(vector<int>& nums, int left, int right) { if (right <= left) return; int mid = left + (right-left)/2; sort(nums, left, mid); sort(nums, mid+1, right); merge(nums, left, mid, right); } void sort(vector<int>& nums) { sort(nums, 0, nums.size()-1); } 7. Quick Sort nt partition(vector<int>& nums, int left, int right) { int pivot = left; int i = left; int j = right+1; while (true) { while (i < right && nums[++i] < nums[pivot]); while (j > left && nums[--j] > nums[pivot]); if (i >= j) break; swap(nums[i], nums[j]); } swap(nums[pivot], nums[j]); return j; } void sort(vector<int>& nums, int left, int right) { if (left >= right) return; int pivot = partition(nums, left, right); sort(nums, left, pivot-1); sort(nums, pivot+1, right); } void sort(vector<int>& nums) { sort(nums, 0, nums.size()-1); } 8. Tim Sort #define MIN_MERGE 32 int minRunLength(int n) { int r = 0; while (n >= MIN_MERGE) { r |= (n & 1); n >>= 1; } return n + r; } void insertionSort(vector<int>& nums, int left, int right) { int n = nums.size(); for (int i = left+1; i <= right; i++) { int j = i-1; int curr = nums[i]; for (; j >= left; j--) { if (nums[j] <= curr) { break; } nums[j+1] = nums[j]; } nums[j+1] = curr; } } void merge(vector<int>& nums, int left, int mid, int right) { int i = left; int j = mid + 1; vector<int> tmp; while (i <= mid && j <= right) { if (nums[i] < nums[j]) tmp.push_back(nums[i++]); else tmp.push_back(nums[j++]); } while (i <= mid) tmp.push_back(nums[i++]); while (j <= right) tmp.push_back(nums[j++]); for (i = left; i <= right; i++) { nums[i] = tmp[i-left]; } } void sort(vector<int>& nums) { int minRun = minRunLength(MIN_MERGE); int n = nums.size(); for (int i = 0; i < n; i += minRun) { int hi = min((i + MIN_MERGE - 1), n-1); insertionSort(nums, i, hi); } for (int size = minRun; size < n; size <<= 1) { for (int left = 0; left < n; left += (size << 1)) { int mid = left + size - 1; int right = min((left + (size << 1) - 1), n-1); if (mid < right) { merge(nums, left, mid, right); } } } } 9. Shell Sort void sort(vector<int>& nums) { int n = nums.size(); for (int gap = n>>1; gap > 0; gap>>=1) { for (int i = gap; i < n; i++) { int tmp = nums[i]; int j; for (j = i; j >= gap && nums[j-gap] > tmp; j -= gap) { nums[j] = nums[j-gap]; } nums[j] = tmp; } } } 10. Counting Sort void sort(vector<int>& nums) { vector<int> dp(10, 0); for (const auto& x : nums) { dp[x]++; } int j = 0; for (int i = 0; i < 10; i++) { while (dp[i]-- > 0) { nums[j++] = i; } } } 回到目錄：[Algo] 演算法筆記 接著閱讀：[Algo] 3-1. Two Pointer/Sliding Window

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

一、回溯法 回溯法與 dfs 相當類似，本質上都是暴力窮舉的演算法，但細微的差異在於： dfs 在遍歷節點。 backtracking 在遍歷樹枝。 站在回溯樹上的一個節點，需要考慮的只有三件事情： 路徑 選擇 終止條件 以全排列問題([Leetcode] 46. permutation)來舉例 全排列問題即給定一組數組 nums，需返回這些數字的所有排列組合，舉例來說，給定一個數組 nums = [1,2,3]，那麼它可能的排列會有： [1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,1,2] [3,2,1] 對應上圖的回溯樹來看，我們在每個樹的節點，都會面臨一次決策，站在樹的根時，相當於我們要選擇排列的第一位，而我們有三個選擇，即 1 或 2 或 3。若我們的第一位選擇了 1，代表我們選擇了 \(\text{x}_1=1\) 的路徑，故接下來我們的選擇只剩下兩個，即 2 或 3。當我們繼續往下做，直到子葉節點時，代表我們已經沒有選擇可選，此時就是我們的終止條件。 回憶我們在二叉樹中練習過前序、中序、後序的思維，前序與後序代表我們在遍歷節點前與後的時間點，而在回溯法，這兩個時間點，各自代表了 將選擇加入路徑 從路徑中撤銷選擇 用二叉樹程式碼來說明即： void traverse(TreeNode* root){ if (!root) return; // preorder: do option traverse(root->left); traverse(root->right); // postorder: retrieve option } N-ary 樹： class Node{ int val; vector<Node*> children; }; void traverse(Node* root){ if (!root) return; for (Node* child : root->children) { // preorder: do option traverse(child); // postorder: retrieve option } } 二、回溯法的框架 藉由上面的思維練習，我們可以拼湊出回溯法的基本框架： vector<Node*> path; vector<vector<Node*>> res; void backtrack(Node* root) { if (terminate_condition) { // 當終止條件時 res.push_back(path); // 將路徑加入結果 return; // 治原路徑返回 } for (auto& next : root->children) { path.push_back(next); // 將選擇加入路徑 backtrack(next); path.pop_back(); // 從路徑中撤銷選擇 } } 試著解題[Leetcode] 46. permutation： void backtrack(vector<int>& nums, vector<bool>& visited, vector<int>& path) { if (path.size() == nums.size()) { res.push_back(path); return; } for (int i = 0; i < nums.size(); i++) { if (visited[i]) continue; visited[i] = true; path.push_back(nums[i]); backtrack(nums, visited, path); visited[i] = false; path.pop_back(); } } 三、例題 1. [Leetcode] 51. N-Queens 經典的 N-Queen 問題，在一個 N x N 的棋盤上，每個橫排、直排與斜線都不能出現 2 個以上的皇后，試求有幾種皇后的排法。 此題就可以用到回溯法，以 4 x 4 的棋盤為例，我們會建構一個深度為 16 的決策樹： 路徑：之前做過的選擇 選擇：選擇要放置皇后，或是不要放置皇后 終止條件：16 個棋格都走完(4列都走完) 注意：因為在第 i 列放了皇后，則同列的其它格子就不能放皇后了，故我們可以直接往第 i+1 列前進。故到了第 n 列，代表達到終止條件。 程式碼： int sz; vector<vector<string>> solveNQueens(int n) { sz = n; vector<vector<string>> res; vector<string> board(n, string(n, '.')); backtrack(board, 0, res); return res; } void backtrack(vector<string>& board, int row, vector<vector<string>>& res){ if (row == sz){ // 終止條件：走完 n 行 res.push_back(board); return; } for (int col = 0; col < sz; col++){ if (!isValid(board, row, col)) continue; board[row][col] = 'Q'; // 放皇后 backtrack(board, row+1, res); board[row][col] = '.'; // 撤銷皇后 } } // 直行、橫列、斜線都不能出線皇后 bool isValid(vector<string>& board, int& row, int& col){ if (row == sz) return true; for (int i = row - 1; i >= 0; i--) if (board[i][col] == 'Q') return false; for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--){ if (board[i][j] == 'Q') return false; } for (int i = row - 1, j = col + 1; i >= 0 && j < sz; i--, j++){ if (board[i][j] == 'Q') return false; } return true; } 2. [Leetcode] 797. All Paths From Source to Target 給定一個 DAG(directed acyclic graph)，各用 0 到 n-1 的數字標示，找出所以可能從 0 走到 n-1 的路徑。其中 graph[i] 代表從 i 可以到達的下一個節點。 vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) { vector<vector<int>> res; vector<int> path; path.push_back(0); // 站在起點 0 backtrack(graph, res, path, 0, -1); return res; } void backtrack(vector<vector<int>>& graph, vector<vector<int>>& res, vector<int>& path, int curr, int last) { if (curr == graph.size()-1) { // 到達終點 n-1 res.push_back(path); return; } for (const auto& next : graph[curr]) { // if (last == next) continue; // 若是 directed 或是 cyclic graph，需要避免走回頭路 path.push_back(next); // 做選擇 backtrack(graph, res, path, next, curr); path.pop_back(); // 做撤銷 } } 3. [Leetcode] 980. Unique Path III 機器人必須走過除了牆外的所有棋格，必且到達指定的位置，試求機器人有幾種走法。其中 1 代表起點。 2 代表終點。 0 代表空白棋格，即機器人必須要經過的棋格。 -1 代表牆，即機器人無須經過且不能經過的棋格。 注意此題的選擇、與撤銷的位置與框架中的前序、後序位置不同，試想會有什麼效果 int res; int uniquePathsIII(vector<vector<int>>& grid) { res = 0; int m = grid.size(), n = grid[0].size(); // 先記錄機器人的起點與終點 pair<int,int> start, end; // 記錄機器人所需走多少步(選擇的次數): 棋格數-障礙-1 int left = m*n; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == 1) { start = {i, j}; left--; } else if (grid[i][j] == -1) { left--; } } } backtrack(grid, start.first, start.second, left); return res; } int dir[4][2] = {{1,0},{0,1},{-1,0},{0,-1}}; void backtrack(vector<vector<int>>& grid, int row, int col, int left) { // 超出棋格、或是已經走過 if (row < 0 || row >= grid.size() || col < 0 || col >= grid[0].size() || grid[row][col] == -1) return; // 終止條件：到達目標且每一個空白棋格都走完(left == 0) if (grid[row][col] == 2 && left == 0) { res++; return; } int tmp = grid[row][col]; // 做選擇 grid[row][col] = -1; // 做標記，代表已走過 for (const auto& d : dir) { backtrack(grid, row+d[0], col+d[1], left-1); } grid[row][col] = tmp; // 做撤銷 } 回到目錄：[Algo] 演算法筆記 想要複習：[Algo] 2-3. 分治法 接著閱讀：[Algo] 2-5. 動態規劃

一、貪心演算法 是一種在每一步都採前當下看起來最好的選擇的一種策略。 由於是當下看起來最好的選擇，故也有可能選到錯的路線，導致最終的答案不是最佳解。 先舉個生活中常見的例子： 今天小明的撲滿裡存滿了大大小小的1塊、5塊跟10塊，今天小明打算要要幫撲滿瘦身，令它的重量降低，那麼小明可以到銀行換鈔，將幣值小、重量重的硬幣集結起來換成幣值大、重量輕的紙鈔。 用貪心演算法的思維，我們一定是從幣值大的 1000 開始換起，再來 500、100、50、10，以此類推，有多少換多少。 // vector<int>& nums = {1000, 500, 100, 50, 10, 5, 1}; vector<int> coinChange(vector<int>& nums, int money) { vector<int> res(nums.size(), 0); for (int i = 0; i < nums.size(); i++) { res[i] += (money / nums[i]); money %= nums[i]; } return res; } 但若我們新增了一個幣值是 23，那麼上面這個思路就有可能會導致錯誤。 貪心演算法的特點 直覺且快速 通常不是最佳的 需要會被要求證明 always stays ahead：跑者每個時間點都在第一名，最後結果會是第一名 用歸納法證明。 exchange argument 用反證法，找到原解的 inversions，並作交換，證明交換後並不影響最佳解。 二、貪心演算法的應用 0. 核心思維 貪心演算法是從某一個初始狀態出發，每次通過選取區域性最優解向目標前進，並最終期望取得整體最優解的一種演算法。由這個定義可知，貪心選擇標準就是選擇當前最好的決策，貪心演算法根據這個標準進行決策，將原問題變成一個相似但規模更小的子問題，而後每一步選出來的一定是原問題整體最優解的一部分。 如果一個問題貪心後只剩下一個子問題且有最優子結構，那麼該問題就可以使用貪心演算法。當一個問題的整體最優解包含其子問題的最優解時，我們稱次問題具有最優子結構性質。 解題一般步驟 設計資料結構並找規律 進心貪心猜想 正確性證明(歸納法證明或是列舉反例進行反證) 實現程式碼 1. 找零錢問題(Coin Change) 先用剛剛提到的那一題來試做： 以貪心法的思維來做就是，幣值愈大先換，換到不能再換時再往次大的幣值換。 vector<int> coinChange(vector<int>& nums, int money) { vector<int> res(nums.size(), 0); for (int i = 0; i < nums.size(); i++) { res[i] += (money / nums[i]); money %= nums[i]; } return res; } 以範例 nums = {1000, 500, 100, 50, 23, 10, 5, 1}，money = 1069 來測試看看，以上述得到的結果應該是：(參考例題Leetcode 322. Coin Change) {1000, 500, 100, 50, 23, 10, 5, 1} = {1, 0, 0, 1, 0, 1, 1, 4}，也就是說，得到的硬幣總數是 8(假設所有幣值都是硬幣)。 因為夾雜了 23，使得問題變得稍微有點不一樣，因為最佳解可以是： {1000, 500, 100, 50, 23, 10, 5, 1} = {1, 0, 0, 0, 3, 0, 0, 0}，總數 4。 從上面此例來觀察，貪心法是需要有適用時機的，當今天少掉 23 的時候，使用貪心法是可以得到最佳解的，因為所有數字互為因數、倍數關係，也就是說，當今天可以用 1 張 1000 解決的情況，必定可以用其它幣值用更多的代價來替換，如 2 張 500，或 10 張 100。但是 23 可以替換的是 2 個 10 塊加上 3 個 1 塊。用數字為例的話如下 \(\boxed{\begin{array}{ll} 1069&=1\times1000+1\times50+1\times10+1\times5+4\times1\\ &=1\times(2\times500)+1\times50+1\times10+1\times5+4\times1\\ &=1\times(10\times100)+1\times50+1\times10+1\times5+4\times1\\ &=1\times(20\times50)+1\times50+1\times10+1\times5+4\times1\\ \end{array}} \) 不管怎麼換，總數都是變大。 如果要解出上述的最佳解，需要做一點修正，或是使用暴力破解法，例如 bfs 來遍歷所有情形來獲得最小值。 試想要怎麼改寫可以使貪法仍然可以適用，「將23拿掉」那麼貪心法就仍可以適用，那要怎麼有技巧的將 23 拿掉呢。 23 能夠有效的替換表示我們一定會使用到 23，也就是說我們可以找到反例使 23 不能有效的替換就好了。 23 = 23*1(1) 換 10*2 + 1*3(5) 46 = 23*2(2) 換 10*4 + 5*1 + 1*1(6) 69 = 23*3(3) 換 50*1 + 10*1 + 1*4(6) 92 = 23*4(4) 換 50*1 + 10*4 + 1*2(7) 115 = 23*5(5) 換 100*1 + 10*1 + 5*1(3) 我們可以發現當 23 替換到第 5 個的時候已經不能有效的替換了，表示我們只有嘗試替換 0~4 個 23 硬幣，其餘剩下的錢用貪心法去計算，仍然可以得到有效的解。(在此只是為了展示失去「局部最佳性」的範例，不做嚴謹的數學證明) 即求 min(f(1069)+0, f(1046)+1, f(1023)+2, f(1000)+3, f(976)+4。 vector<int> coinChange(vector<int>&nums, int money) { ... } // implement by greedy vector<int> coinChangePlus(vector<int>&nums, int money) { vector<int> res; int coins = INT_MAX; for (int i = 0; i <= 4; i++) { vector<int> tmp = coinChange(nums, money-23*i); tmp[4]+=i; int cnt = accumulate(tmp.begin(), tmp.end(), 0); if (cnt < coins) { res = tmp; coins = cnt; } } return res; } 以上方法當遇到單一奇異數(無因倍數關係)的時候還可以用，但遇到多個奇異數的時候，複雜度就會明顯上升，到時後我們會遇用其它方法來解構。在後面的動態規劃篇，有深入的介紹，如何利用其它技巧達到剪枝得到最佳解。 由此可發現，貪心法不一定會得到最佳解，需要嚴格的驗證「局部最佳性」，才能保證最後的解是最佳解。 2. 背包問題(Knapsack Problem) 常見的背包問題分為分數背包問題與0-1背包問題。 今天在某個場合，你有一個載重5kg的背包，面前有3kg的金沙、3kg的銀沙與2kg的銅沙，已知金的價格比銀高，銀的價格比銅高。你可以任意決定怎麼將它們裝進背包，最後換取對應價值的獎金，試問怎麼裝可以得到最高的獎金？ 同樣的場合，金沙、銀沙、銅沙換成了金塊、銀塊、銅塊，分別也是 3kg、3kg、2kg，且不可切割，試問要怎麼裝可以得到最高的獎金？ 第1題(分數背包)，顯而易見，用貪心法來做一定是盡可能先裝滿價值高的金沙，再用剩餘的空間以此類推裝填其它的。(3kg金沙+2kg銀沙) 第2題(0-1背包)，由於拿完金塊，無法再拿銀塊，所以最佳解變成了拿金塊與銅塊。(3kg金塊+2kg銅塊) 三、例題 1. 餅乾分配問題 Leetcode 455. Assign Cookies 有若干個不同份量的餅乾，與若干個需要不同份量才能滿足的小孩，試問餅乾最多可以讓幾個小孩滿意。 把餅乾的份量從小排到大，把小孩從需求小排到需求大。 盡可能的滿足需求小的小孩。(若需求小的都滿足不了，那麼需求大的就不可能滿足了) int findContentChildren(vector<int>& children, vector<int>& cookies) { sort(children.begin(), children.end()); sort(cookies.begin(), cookies.end()); int child = 0, cookie = 0; while (child < children.size() && cookie < cookies.size()) { if (children[child] <= cookies[cookie]) child++; cookie++; } return child; } 2. 股票買賣問題 Leetcode 122. Best Timer to Buy and Sell Stock II 有一數列為某上市公司每日的股價，若手上最多只能有一張股票，要怎麼樣買賣可以得到最高獲利。 最高獲利代表所有上升波段的總和，忽略所有下降波段。 int maxProfit(vector<int>& prices) { int sum = 0; int last = prices[0]; for (const auto& price : prices) { sum += (price > last) ? price - last : 0; last = price } return sum; } 3. 跳躍遊戲 55. Jump Game 有一數列表示，在該 i 索引位置起，最多可以跳幾個索引長度，試問從索引值為 0 開始，可否到達索引值為 n-1。 盡可能的往前跳，不斷的更新最遠可以到達的位置。 bool canJump(vector<int>& nums) { int reach = nums[0]; for (int i = 0; i < nums.size() && i <= reach; i++) { if (i == nums.size()-1) return true; reach = max(reach, nums[i]+i); } return false; } 回到目錄：[Algo] 演算法筆記 想要複習：[Algo] 2-1. 暴力演算法 接著閱讀：[Algo] 2-3. 分治法

一、暴力演算法 暴力演算法就是枚舉法，試想今天有一個行李箱的密碼鎖為四個一組，但你又忘記密碼，那要怎麼辦？你會試著從 0000 轉到 9999 共 10000 種組合都試過，必定會找出密碼，把所有可能都枚舉過一遍，遍是暴力演算法。 暴力演算法可以應用於很多問題，包含數論、樹、圖論等等，而暴力演算法的重點在於枚舉所有可能，以樹來說就是樹的遍歷。 舉例來說： Leetcode 1. Two Sum 給定一個數列，找數列中任兩個數的和為 target，回傳兩個數的索引值。 在還沒有認識任何資料結構之前，我們能想到最簡單的方法就是遍歷整個數列，用兩個指標 i 與 j，各指向一個數，將所有可能檢查過一遍，直到找到目標。 vector<int> twoSum(vector<int>& nums, int target) { for (int i = 0; i < nums.size() - 1; i++) for (int j = i + 1; j < nums.size(); j++) if (nums[i] + nums[j] == target) return {i, j}; return {-1, -1}; } 以上例來說，用暴力破解法求解時，求兩數和的時候，我們需進行兩個維度的 for-loop 迴圈來求解。若進一步到三數和、四數和、五數和時，我們會發現，維度會隨著多少個數字和增加。也就是三數和為 3 個迴圈，四數和為 4 個迴圈，以此類推。 以 複雜度分析 Algorithmic complexity / Big-O / Asymptotic analysis來分析，也就相當於 k 數和的時間複雜度為 \(O(n^k)\)，這個增長是相當恐怖的。 暴力演算法的特點 簡單粗暴 將所有可能枚舉出來，藉由電腦的運算力高於人腦的特性。 執行效率低 由於所有的情形都需列舉出來，所以執行效率低。 只適用於規模小的問題。 可作用衡量效率問題的基礎算法 暴力法可以看成是某問題時間效能的底限，所以可以用來衡量其它演算法的效率。 二、暴力演算法應用 1. 數組 線性搜索法(Linear Search) 將一個資料集合的所有元素遍歷一次，找到所需的目標。 例：有一個數列共有 n 個元素，找數列中是否含有某數 target，若有則回傳其索引值，若無則回傳 -1。 int findTarget(vector<int>& nums, int target) { for (int i = 0; i < nums.size(); i++) { if (nums[i] == target) return i; } return -1; } 2. 樹 ...

algorithm <algorithm> 定義了專為元素集合設計的函式。 元素集合包含可以被迭代器或指標存取的一系列元素，例如陣列或 STL container。但且注意，演算法只會透過迭代器去操作容器中的值，並不會更改其結構或是大小。 一、函式 1. 無修改值的操作 all_of bool all_of(Iterator first, Iterator last, UnaryPredicate pred) 檢查是否全部的元素都符合判斷式。 #include <iostream> #include <vector> #include <algorithm> using namespace std; int main(){ vector<int> arr1 = {1,2,3,4,5}; vector<int> arr2 = {1,3,5,7,9}; vector<int> arr3 = {2,4,6,8,10}; auto isodd = [](int x)->bool{ return x%2; }; cout << all_of(arr1.begin(), arr1.end(), isodd) << endl; // 0 cout << all_of(arr2.begin(), arr2.end(), isodd) << endl; // 1 cout << all_of(arr3.begin(), arr3.end(), isodd) << endl; // 0 return 0; } any_of bool any_of(Iterator first, Iterator last, Predicate pred) ...

一、動態規劃的思考藝術 動態規劃其實就是一種暴力枚舉的優化，在暴力枚舉的過程中有著大量的重複，藉由「備忘錄(memoization)」的方式做到剪枝(pruning)來達到優化的一種演算法。 舉例來說： Leetcode 62. Unique Paths 機器人由左上走到右下角星星有幾種走法，其中機器人只能選擇往右走或往下走。 試想機器人從 (1,1) 走到 (m,n) 的不同路徑中，可見有大量的重複，比如過程中有一點 (i,j)，其 (1,1) 走到 (i,j) 有 k 條不同路徑，麼那對於任何一條固定 (i,j) 到 (m,n) 的路徑，都需走 k 遍來模擬。 但其實我們不必關心具體的走法，我們只關心狀態，也就是走法的數目。 同理，我們若知道 (i,j) 到 (m,n) 共有 t 條不同的路徑，那麼 (1,1) -> (i,j) -> (m,n) 的不同路徑總數就是 k*s。 我們知道最左邊那欄與最上面那列都只有可能有一種路徑可以走，又每一格的路徑來自於上方與左方的和： sum of (i,j) = sum of (i-1,j) + sum of (i,j-1) \(\begin{array}{|c|c|c|c|c|c|c|}\hline \text{1}&\text{1}&\text{1}&\text{1}&\text{1}&\text{1}&\text{1}\\\hline \text{1}&\text{2}&\text{3}&\text{4}&\text{5}&\text{6}&\text{7}\\\hline \text{1}&\text{3}&\text{6}&\text{10}&\text{15}&\text{21}&\text{28}\\\hline \end{array}\) 寫成程式碼就是 int uniquePaths(int m, int n) { vector<vector<int>> dp(m+1, vector<int>(n+1,0)); for (int i = 1; i <= m; i++) // 將第一列填成 1 dp[i][1] = 1; for (int j = 1; j <= n; j++) // 將第一欄填成 1 dp[1][j] = 1; for (int i = 2; i <= m; i++) { // 將剩下的格子填完 for (int j = 2; j <= n; j++) { dp[i][j] = dp[i-1][j] + dp[i][j-1]; } } return dp[m][n]; } 注意填格子的順序是有一定的限制的，必須要確保相關聯的子問題已經處理過。 動態規劃 由上例我們可以發現，原本的問題可以拆解成更小的問題(從 (1,1)->(m,n) 變成從 (1,1)->(i,j) 和從 (i,j)->(m,n))。 我們令 f(i,j) 表示從 (1,1)->(i,j) 的不同路徑數，則我們可以得到轉移方程式 f(i,j)=f(i-1,j)+f(i,j-1)。 我們發現，想求出 f(i,j) 只需要知道幾個更小的 f(i',j')。我們將 f(i',j') 稱為子問題。 我們捨棄冗餘的訊息(具體的走法)，只記錄對解決問題有幫助的結果。 動態規劃的兩大特點(適用前提) 無後效性 一旦 f(i,j) 確定，就不用關心我們如何計算出 f(i,j) 想要確定 f(i,j)，只需要知道 f(i-1,j) 和 f(i,j-1) 的值，而至於它們是如何算出來的，對當前或之後的任何子問題都沒有影響。 過去不依賴未來，未來不影響過去。 最優子結構 f(i,j) 的定義就已經蘊含了最優。 大問題的最優解可以由若干個小問題的最優解推出。(max, min, sum…) DP 能適用於：能將大問題拆成若干小問題，滿足無後效性、最優子結構性質。 以下介紹幾種刷題會遇到的動態規劃套路： 二、動態規劃框架 1. 定序列型 ...