CS

一、Big O 表示法 Big O 的數學定義： \(\boxed{O(g(n)) = \lbrace{f(n):存在正常量\space c\space 和\space n_0，使得對所有\space n\ge n_0，有\space 0 \le f(n) \le cg(n)\rbrace}}\) 我們常用的 big O 表示法中的 \(O\) 其實代表了一個函數的集合，比方說 \(O(n^2)\) 代表著一個由 \(g(n) = n^2\) 派生出來的一個函數集合；我們說一個演算法的時間複雜度為 \(O(n^2)\)，意思就是描述該演算法的複雜度函數屬於這個函數集合之中。 分析複雜度時，常用的兩個特性： 只保留增長速率最快的項，其它省略 \(\boxed{O(2n+100) = O(n)}\) \(\boxed{O(2^{n+1}) = O(2^n)}\) \(\boxed{O(m+3n+99) = O(m+n)}\) \(\boxed{O(n^3+999\times n^2+999\times n) = O(n^3)}\) Big O 記號表示複雜度的「上限」 換句話說，只要給出的是一個上限，用 Big O 表示法都是正確的。 但在習慣上，我們特別取最緊臨的上限。但若複雜度會跟算法的輸入數據有關，沒辦法提前給出一個特別精確的時間複雜度時，擴大時間複雜度的上限就變得有意義了。 例如湊零錢問題中，金額 amount 的值為 n，coins 列表中的個數為 k，則這棵遞迴樹就是 K 叉樹。而節點的數量與樹的結構有關，而我們無法提前知道樹的結構，所以我們按照最壞情形來處理，高度為 n 的一棵滿 k 叉樹，其節點數為 \(\frac{k^n-1}{k-1}\)，用 big O 表示就是 \(O(k^n)\)。 二、主定理(Master Theorem) 有時候時間複雜度的判斷沒那麼容易，主定理是一個數學推導的方法：可以參考網站https://brilliant....

一、二叉樹的思維模式 二叉樹的解題模式大致分為兩類： 是否可以通過遍歷一遍得解 是否可以定義一個遞迴函數，通過分治法推導出原問題的答案？ [LeetCode. 104] Maximum Depth of Binary Tree(Easy) 以此題為例，可以遍歷完整個樹，並比較當下的樹的深度，得以求解。 int depth = 0; int maxDepth(TreeNode* root){ traverse(root, 1); return depth; } void traverse(TreeNode* root, int currDepth){ if (!root) return; traverse(root->left, currDepth+1); depth = max(depth, currDepth); traverse(root->right, currDepth+1); } 若想辦法定義一個遞迴函數，通過分治法推導出原問題，換言之，就是先處理更小的樹，再藉由小的樹處理大的樹： int maxDepth(TreeNode* root) { if (root == NULL) return 0; return 1 + max(maxDepth(root->left), maxDepth(root->right)); } 事實上，兩個思維模式便對應著兩種演算法：回溯法(back tracking)與動態規劃(dynamic programming) 二、前序、中序、後序 無論使用哪種思維模式(遍歷或找出遞迴函數)，都要思考單獨抽出一個節點，它需要在何時(前、中、後序)做哪些事情，其它的節點交由遞迴函數去執行相同的操作。 以下我們以 quick sort 與 merge sort 為例，同樣是分治法，看看在數組上有什麼同樣的思維模式。 quick sort 從 sort() 函式便可見類似於前序的結構。 void sort(vector<int>& nums, int left, int right){ if (left >= right) return; // 終止條件 int mid = partition(nums, left, right); // 做什麼事(pre-order) sort(nums, left, mid-1); // 左子樹 sort(nums, mid+1, right); // 右子樹 } int partition(vector<int>& nums, int left, int right){ int pivot = right; while (left < right){ while (nums[left] < nums[pivot]) left++; while (nums[right] > nums[pivot]) right--; if (left < right) swap(nums[left], nums[right]); } if (left == right && nums[left] > nums[pivot] || nums[right] < nums[pivot]){ swap(nums[left], pivot); return left; } return pivot; } merge sort 從 sort() 函式便可見類似於後序的結構。 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); // 做什麼事(post-order) } void merge(vector<int>& nums, int left, int mid, int right){ vector<int> vec; int i = left, j = mid+1; while (i <= mid && j <= right){ int x = nums[i] < nums[j] ?...

一、鏈表的基本結構 鏈表是由節點和指針構成的數據結構，每個節點存有一個值，和一個指向下一個節點的指針。不同於數組，鏈表並不能隨機訪問，必須透過指針找到該節點才能獲取其值；同理在未遍歷到鏈表結尾時，我們也無法知道鏈表長度，除非依賴其它數據結構儲存長度。 LeetCode 中默認的鏈表： struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(nullptr) {} }; 二、鏈表的基本操作 在開始演算法實踐前，先來練習一下鏈表的 CRUD 吧！ 1. 查(Read) 由於鏈表並非在儲存格中連續分布，所以無法用索引進行隨機訪問，所以我們必須逐個訪問，直到到達我們想要的元素。 藉由指針每次指向當前節點的 next，移動 n 次到達 index 為 n 的節點。 int at(ListNode* head, int n){ // index 為 n ListNode* curr = head; while (n--){ // 移動 n 次 curr = curr->next; } return curr->val; } 2. 改(Update) 改的步驟，只是將查完的元素予以賦值。 void update(ListNode* head, int n, int val){ ListNode* curr = head; while (n--){ curr = curr->next; } curr->val = val; // 查完後賦值 } 3....

一、資料結構概要 資料結構的存儲方式大體上只分為兩種： Array、Linked List。 雖說資料結構有 disjoint matrix, queue, stack, tree, graph 等等，但它們都可以視為 Array 與 Linked List 的上層結構，可以看成是以 Array 或 Linked List 為基底上的操作，只是 API 不同而已。 Array：由於是緊湊連續儲存的，可以隨機訪問，通過 index 快速找到對應元素，且相對節約空間。但也因必須一次性分配儲存空間，所以 array 如果需要擴充容量，就必須再重新分配一塊更大的空間，再把數孛複製過去，其時間複雜度為 \(O(N)\)；在 array 中間進行 delete 與 insert，必須搬移後面所有數據以保持連續，故時間複雜度也為\(O(N)\)。 Linked List：因為元素不連續，而是靠指針指向下一個元素的位置，所以不存在 array 的擴充容量的問題，如果知道某一元素的前一個節點與後一個節點，操作指針即可刪除該元素或者插入新元素，時間複雜度為\(O(1)\)。但正因為儲存空間不連續，無法根擇 index 算出對應元素的地址，所以不能隨機訪問；而且由於每個元素必須額外儲存前後元素位置的指針，相對較耗空間。 在 C、C++ 語言中，指針(pointer)的存在使得其能更直接對儲存空間的位址做操作，所以在處理 C 語言時，要額外了解指針的運作方式。 二、資料結構的基本操作 資料結構的基本操作不外乎： 遍歷(traverse)、增減查改(CRUD, create, read, update, delete) Array：數組的遍歷框架 -> 典型的線性迭代結構： void traverse(vector<int> arr){ for (int i = 0; i < arr.size(); i++){ // iteration } } ListNode：鏈表的遍歷框架 -> 兼具迭代與遞迴 class ListNode { public: int val; ListNode* next; }; void traverse(ListNode* head){ for (ListNode curr = head; curr !...

From the begining: Washam’s Coding Interview University 演算法 Leetcode 演算法筆記 程式語言 C# 計算機結構 計算機結構 作業系統 計算機作業系統 網路 計算機網路 HTTP Socket 資料庫 資料庫系統原理 SQL 語法 NoSQL Redis 系統設計 系統架構 系統設計基礎 分布式 集群 駭客技術 緩存 訊息佇列 物件導向 物件導向概念 設計模式 工具 Git Docker Kubernetes MVC 程式碼實踐 重構(Refactoring) Google Coding Style(C++)