Data Structures and Algorithms

How to find all primes under n? Sieve of Eratosthenes This algorithm is a very intuitive way to find all primes under n. We first create a list of numbers from 2 to n and then iterate over the list. For each number i, we mark all its multiples as non-prime. At the end, all numbers that are not marked are prime. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 vector<int> find_primes(int n) { vector<int> primes; vector<bool> is_prime(n + 1, true); for (int i = 2; i * i <= n; i++) { if (is_prime[i]) { for (int j = i * i; j <= n; j += i) { is_prime[j] = false; } } } for (int i = 2; i <= n; i++) { if (is_prime[i]) { primes.push_back(i); } } return primes; } Let’s analyze the time complexity. For each prime number p, we will iterate from p * p to n. Which means that the time complexity is $\sum_{p \text{ is prime}}^{p \leq n} \frac{n}{p} = n\sum_{p \text{ is prime}}^{p \leq n} \frac{1}{p} = n\log\log n$ (prime harmonic series). ...

問題描述 給定一個大小為 n 的整數陣列，如何找到出現頻率大於（必須嚴格大於）n/2 的元素？ 例如：arr = [1, 1, 2]，那麼 1 就是出現頻率大於 n/2 的元素。 如果 arr = [1, 1, 3, 4]，那麼不存在這樣的元素。 Boyer–Moore majority vote algorithm 一個很直覺的方法就是用一個 hash map 計算所有數字出現的頻率，然後找出出現最多次的元素。需要 O(n) 的空間複雜度以及 O(n) 的時間複雜度。但是用 Boyer-Moore algorithm，只要 O(1) 的空間複雜度即可。來看看這個演算法是如何辦到的。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 int majorityElement(vector<int>& nums) { int candidate = 0; int freq = 0; for (int i = 0; i < nums.size(); i++){ if (candidate == nums[i]){ freq++; } else if (freq == 0){ candidate = nums[i]; freq = 1; } else { freq--; } } return candidate; } candidate 是答案的候選人，而 freq 則是 candidate 出現的頻率。 ...

今天來複習一下常見遍歷樹的方式。 Recursive way Inorder traversal 先拜訪 left subtree，再依序拜訪 root node 跟 right subtree。 void Inorder_traversal(TreeNode *node){ if (node == NULL){ return; } Inorder_traversal(node->left); cout << node->val << " "; Inorder_traversal(node->rihgt); return; } Preorder traversal 先拜訪 root node，再依序拜訪 left subtree 跟 right subtree。 void Preorder_traversal(TreeNode *node){ if (node == NULL){ return; } cout << node->val << " "; Preorder_traversal(node->left); Preorder_traversal(node->rihgt); return; } Postorder traversal 先依序拜訪 left subtree 跟 right subtree，再拜訪 root node。 void Postorder_traversal(TreeNode *node){ if (node == NULL){ return; } Postorder_traversal(node->left); Postorder_traversal(node->rihgt); cout << node->val << " "; return; } 可以看到用 recursive 寫的話，三種方式的 code 基本上長一樣，而且複雜度也都一樣，只是差在遍歷 root node 的時間不一樣。 time complexity: $O(n)$ space complextiy: $O(h)$, where $h = $ tree height ...

這是在寫 1799. Maximize Score After N Operations 時遇到的問題。 簡單來說，我想要解決的問題是「找到 n 個物品中取 k 個的所有組合」。而 Gosper’s Hack 可以有效率地找到 n 個 bit 中 k 個 bit 爲 1 的所有組合，剛剛好對應了我的問題。 Gosper’s Hack 的原理就是，從滿足條件（n 個 bit 中 k 個 bit 爲 1）的數字中，從最小的數字，一路找到最大的。 如果想找「5 個 bit 中 2 個 bit 爲 1」的組合，那麼 Gosper’s Hack 會依序找到 00011 00101 00110 01001 01010 01100 10001 10010 10100 11000 首先，滿足條件的數字中，最小的數字很容易就找到，就是把所有的 1 塞到最右邊去，也就是 int state = (1 << k) - 1; 接下來比較難的問題是，要如何有效率地找到下一個數字。 找到下一個數字，分成兩個步驟 把最右邊的 $01$ 變成 $10$ 把剛剛 $10$ 右邊的 $1$ 全部推到最右邊去 看一個範例：有數字 $10011110_2$，他的下一個數字應該是多少？ 根據上面的步驟，$10011100_2$ 的下一個數字就是 $10100111_2$ ...