Algo

一、回溯法 回溯法與 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 (!...

一、分治法 分治法，簡而言之就是分而治之，把複雜的問題分成兩個或更多個相似或相似的子問題，直到子問題可以直接求解，最後再將子問題的解做合併。 三步驟：Divide、Conquer、Merge 以 pseudo code 來表示大概像： void func(collection set) { // 子問題求解 if (base_case) { // 根據要求將子問題解合併成母問題解 do_something return; } // 將母問題分解成子問題 for (collection subset : set) { func(subset); } } graph LR; 母問題-->子問題1; 母問題-->子問題2; subgraph Divide 子問題1-->最小子問題1; 子問題1-->最小子問題2; 子問題2-->最小子問題3; 子問題2-->最小子問題4; end subgraph Conquer 最小子問題1-->最小子問題解1; 最小子問題2-->最小子問題解2; 最小子問題3-->最小子問題解3; 最小子問題4-->最小子問題解4; end subgraph Merge 最小子問題解1-->合併; 最小子問題解2-->合併; 最小子問題解3-->合併; 最小子問題解4-->合併; end 合併-->母問題解 舉例說明，河內塔遊戲： 河內塔是由三根桿子以大小不同碟片所組成的遊戲，僧人一次可以從一根桿子移動一個碟片到另一根桿子，但是小的碟片若放憂大的碟片下面會使得小的碟片裂開(也就是碟片只能由上而下從小排到大)，試問將一座塔從一根桿子完整的移動到另一根桿子需要移動多少次。 思考上面的情形，以三個碟片為例，若我們要從 A 到 C 移動一座塔，我們可以將之分解成「如何把上面兩個碟片移動到 B」，因為剩下的一個大碟片，可以很簡單的從 A 移動到 C。也就是說 f3(A->C) = f2(A->B) + f1(A->C) + f2(B->C)。 再更進一步，f2(A->B) 和 f2(B->C) 其實就是移動兩個碟片到另一座塔，所以可以分解成 f2(A->C) = f1(A->B) + f1(A->C) + f1(B->C)，至此，我們已經把 f3 都分解成可以代表一次移動的最小子問題的解 f1 了： graph TD; A[f3,A->C] B[f2,A->B] C[f1,A->C] D[f2,B->C] E[f1,A->C] F[f1,A->B] G[f1,C->B] H[f1,B->A] I[f1,B->C] J[f1,A->C] A-->B A--->C A-->D B-->E B-->F B-->G D-->H D-->I D-->J 故我們可以以數學方式證明：...

一、貪心演算法 是一種在每一步都採前當下看起來最好的選擇的一種策略。 由於是當下看起來最好的選擇，故也有可能選到錯的路線，導致最終的答案不是最佳解。 先舉個生活中常見的例子： 今天小明的撲滿裡存滿了大大小小的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....

一、暴力演算法 暴力演算法就是枚舉法，試想今天有一個行李箱的密碼鎖為四個一組，但你又忘記密碼，那要怎麼辦？你會試著從 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)\)，這個增長是相當恐怖的。 暴力演算法的特點...

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....