題目： LeetCode - 952. Largest Component Size by Common Factor 題目說明待編輯… 解題思路待編輯… 參考解法12345678910111213141516171819202122232425class DSU{public: DSU(int n) : p(n) { for(int i = 0; i < n; ++i) p[i] = i; } void _union(int x, int y) { p[_find(x)] = p[_find(y)]; } int _find(int x) { if(p[x] != x) p[x] = _find(p[x]); return p[x]; }private: vector<int> p;};class Solution {public: int largestComponentSize(vector<int>& ...

題目： LeetCode - 969. Pancake Sorting 題目說明利用煎餅排序將一個陣列排序好。並回傳每次翻轉的個數。 解題思路由於前面翻轉並不會影響到後面的排序，所以主要想法為每次將最大的排序到後面，接著都只翻轉前面，最後即可完成排序。使用 find() 找到當前要找的值的位置，接著翻轉一次，此時最大的值會在陣列的最前面，接著翻轉一次將這個值翻轉到後面即可。 參考解法123456789101112131415class Solution {public: vector<int> pancakeSort(vector<int>& A) { vector<int>v; for(int i = A.size(); i > 0; --i) { int pos = find(A.begin(), A.end(), i) - A.begin(); reverse(A.begin(), A.begin() + ...

題目： LeetCode - 470. Implement Rand10() Using Rand7() 題目說明給一個 rand7() 會隨機回傳 1 ~ 7 整數的函式 ( 機率相等 )，要求完成 rand10()。題目要求不要使用函式庫的 rand() 函數。 解題思路數學問題，取兩次 rand7() 會得到一個 7 * 7 的矩形，前面 40 個可以透過 (7 * (rand7() - 1) + (rand7() - 1)) % 10 + 1 的計算取得 1 ~ 10 的數字且機率相同，若是取得後面 9 個就要重新取。 參考解法12345678class Solution {public: int rand10() { int idx = 41; while(idx >= 40) idx = 7 * (rand7() - 1) + (rand7() - 1); return idx % 10 + 1; }};

題目： LeetCode - 436. Find Right Interval 題目說明給一堆區間，求每個區間的最近右邊區間的索引號 ( 右邊區間的 start >= 左邊區間的 end)，若不存在則為 -1。 解題思路使用 map 紀錄每個區間的起始點及索引號，接著遍歷所有區間，使用 lower_bound() 實現二分查找。 參考解法1234567891011121314151617181920// fast IOstatic auto __ = [](){ std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); return 0;}();class Solution {public: vector<int> findRightInterval(vector<vector<int>>& intervals) { vector< ...

題目： LeetCode - 8. String to Integer (atoi) 題目說明定義一個自己的 atoi() 函數。 字串前面的空白需忽視 正負號只看最前面的符號 若超過範圍則回傳最大值或最小值 解題思路使用 String 的 find_first_not_of() 來去除前面的空白，接著先檢查是否有正負號，之後將數字存入即可。( 這邊使用 long 是為了避免越界 ) 參考解法123456789101112131415class Solution {public: int myAtoi(string str) { long res = 0; int indicator = 1, mx = INT_MAX, idx = str.find_first_not_of(' '); if(idx == -1) return 0; if(str[idx] == '+' || str[idx] == '-') indicator = str ...

題目： LeetCode - 412. Fizz Buzz 題目說明給一個整數 n，要求回傳一個字串的陣列，i 從 1 數到 n，若 i 為 3 的倍數，字串為 “Fizz”，若為 5 的倍數則為 “Buzz”，若為 3 與 5 的倍數則為 “FizzBuzz”，否則為 i。 解題思路字串的串接。 參考解法123456789101112131415class Solution {public: vector<string> fizzBuzz(int n) { vector<string> v; for(int i = 1; i <= n; ++i) { string tmp; if(!(i % 3)) tmp += "Fizz"; if(!(i % 5)) tmp += "Buzz"; if(tmp.empty()) tmp += to_string ...

題目： LeetCode - 23. Merge k Sorted Lists 題目說明給 k 個已經由小到大排序好的 Lists，將全部合成一個由小到大排序的 List。 解題思路使用 priority_queue 幫我們排序，由於是自定義的型態，所以需要自己寫比較函數。先遍歷一次 lists 將所有 list 的 head 都推入，接著將 pq.top() 連接，若 pq.top()->next 存在，就重新推入。 參考解法123456789101112131415class Solution {public: ListNode* mergeKLists(vector<ListNode*>& lists) { auto cmp = [](ListNode* l, ListNode* r) { return l->val > r->val; }; priority_queue<ListNode*, vector<ListNode*>, declt ...

題目： LeetCode - 983. Minimum Cost For Tickets 題目說明給兩個陣列，days 代表需要坐火車的日期，costs 代表火車的日票、周票、月票價格。求所有需要搭火車的日期都能搭火車的最小花費。 解題思路動態規劃，若當天需要搭火車，最佳解為 當天買一張日票、六天前買一張周票、29天前買一張月票，三者的價格的最小值。若當天不需要搭火車，價格就為前一天的價格。 參考解法12345678910111213class Solution {public: int mincostTickets(vector<int>& days, vector<int>& costs) { vector<int> dp(days.back() + 1); unordered_set<int> set(days.begin(), days.end()); for(int i = 1; i <= days.back(); ++i) ...

題目： LeetCode - 404. Sum of Left Leaves 題目說明給一個 Tree，找到所有位於左邊的葉子的總和。 解題思路判斷當前 node 的左邊 node 是否符合 !root->left->left && !root->left->right 若符合代表 root->left 為左邊的葉子，依此想法使用遞迴即可。 參考解法12345678class Solution {public: int sumOfLeftLeaves(TreeNode* root) { if(!root) return 0; if(root->left && !root->left->left && !root->left->right) return root->left->val + sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->righ ...

題目： LeetCode - 1032. Stream of Characters 題目說明完成一個 Class，裡面包含兩個函式。 StreamChecker(vector<string>& words)：給一個字串的陣列，表示字典。 bool query(char letter)：可以想像成呼叫一次就是使用者打了一個字，檢查使用者打的前幾個字中是否有包含於字典中的單詞。 解題思路使用字典樹來實現，關於字典樹的做法可參考本篇文章：LeeCode - 208 解題紀錄 及 本篇文章：LeeCode - 211 解題紀錄 只要建一個顛倒的字典樹即可。例如 cd 就建成 dc。 StreamChecker(vector<string>& words)：普通字典樹的建造。 bool query(char letter)：呼叫時先將 letter 加入到字串中，接著從後面開始往前檢查。 參考解法12345678910111213141516171819202122232425262728293031323334353637383940414243 ...