題目： LeetCode - 1286. Iterator for Combination 題目說明設計一個 Class，並完成題目要求完成的函式。 CombinationIterator(string characters, int combinationLength)：Constructor，characters 為排序好的字串並且每個字元只會出現一次，combinationLength 為組合的長度。 next()： 按照字典序返回長度為 combinationLength 的下一個排列。 hasNext()： 返回是否還能形成下一個排序。 解題思路其實就是排序的問題，最小的情況就是 characters 的前 combinationLength 個字元，最大的情況就是 characters 的倒數 combinationLength 個字元。 CombinationIterator(string characters, int combinationLength)： 在構造的時候我們把最小的情況放入 cur，最大的情況放入 last，並紀錄原本的 characters ...

題目： LeetCode - 119. Pascal’s Triangle II 題目說明給一個整數 rowIndex，求第 rowIndex 層 ( 從 0 開始 ) 的帕斯卡三角形的值。( 回傳一個陣列 )※ 題目希望空間複雜度為 O(rowIndex)。 解題思路當我們將帕斯卡三角形轉換成陣列的表示方法時： 123411 11 2 11 3 3 1 會發現對於 pascal[i][j] 來說，其值為 pascal[i - 1][j] + pascal[i - 1][j - 1]。而題目只要求特定的某一層，所以我們從後面開始做就可以省掉上面層數的空間。 參考解法123456789class Solution {public: vector<int> getRow(int rowIndex) { vector<int> v(rowIndex + 1); v[0] = 1; for(int i = 0; i < rowIndex; ++i) for(int j = i + 1; j &g ...

題目： LeetCode - 274. H-Index 題目說明給一個陣列，代表每篇論文的引用數，求 H - index。( 若 h = 5，代表有 5 篇論文的引用數大於等於 5，其餘論文的引用數皆小於 5 ) 解題思路先將陣列降冪排序，接著遍歷陣列，若 citations[i] >= i + 1，代表有 i + 1 篇論文的引用數大於等於 i + 1，持續做直到找到最大的 h 即可。( 當找到最大的 h 代表總共有 h 篇論文的引用數大於等於 h，而後面論文的引用數都小於 h ) 12345678Example:[3,0,6,1,5][6,5,3,1,0] // sortedi = 0, citations[0] = 6 >= 1, 代表目前有 1 篇論文的引用數大於等於 1i = 1, citations[1] = 5 >= 2, 代表目前有 2 篇論文的引用數大於等於 2i = 2, citations[2] = 3 >= 3, 代表目前有 3 篇論文的引用數大於等於 3i = 3, citations[3] = 1 < 4, 其實做到這邊就 ...

題目： LeetCode - 171. Excel Sheet Column Number 題目說明給一個只含有大寫英文字母的字串，按照題目的規則求出對應的數字。 解題思路想像為 26 進制即可，例如 "AAA" = (1 * 26²) + (1 * 26¹) + (1 * 26⁰)。 參考解法123456789class Solution {public: int titleToNumber(string s) { int n = s.size() - 1, res = 0; for(auto c : s) res += (c - 'A' + 1) * pow(26, n--); return res; }};

題目： LeetCode - 994. Rotting Oranges 題目說明給一個二維陣列，裡面只含有 0、1、2。0 代表該座標沒有東西，1 代表該座標有一顆正常的橘子，2 代表該座標有一顆腐敗的橘子，腐敗的橘子每經過一天會使得上下左右四顆橘子也腐敗，求讓所有橘子都腐敗需要的天數，若無法使所有橘子腐敗就回傳 -1。 解題思路先遍歷一次整個陣列，紀錄新鮮橘子的個數，腐敗橘子的座標使用 Queue 存放。接著把所有座標拿出並感染上下左右正常的橘子，再把新腐敗的橘子座標存入 Queue，清空一次 Queue 代表經過了一天，最後判斷是否還有未腐敗的橘子即可。 參考解法12345678910111213141516171819202122232425262728293031class Solution {public: int orangesRotting(vector<vector<int>>& grid) { int height = grid.size(), width = grid[0].size(), fr ...

題目： LeetCode - 437. Path Sum III 題目說明給一個 Tree、一個整數 sum，求樹中有幾段子樹的路徑和為 sum。 解題思路遍歷整棵樹，currSum 紀錄從 root 到當前節點的路徑和，由於 currSum - (currSum - target) = target，所以只要看前面有幾種路徑和的值為 currSum - target 就可以得到以當前節點為終點的子樹路徑和為 sum 的個數，將次數加上 count 即可。 參考解法123456789101112131415161718192021222324252627282930// fast IOstatic auto __ = [](){ std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); return 0;}();class Solution {public: int pathSum(TreeNode* root ...

題目： LeetCode - 21. Merge Two Sorted Lists 題目說明給兩個 List，將數值從小到大排序。 解題思路使用遞迴即可，每次都以較小的值建立 node。 參考解法12345678class Solution {public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { if(!l1) return l2; if(!l2) return l1; return l1->val < l2->val ? new ListNode(l1->val, mergeTwoLists(l1->next, l2)) : new ListNode(l2->val, mergeTwoLists(l1, l2->next)); }};

題目： LeetCode - 987. Vertical Order Traversal of a Binary Tree 題目說明給一個 Binary Tree，將 Tree 加上虛擬座標，root 為 (0, 0)，左邊節點為 (x - 1, y - 1)，右邊節點為 (x + 1, y - 1)。求從 x 的最小值到 x 的最大值中的元素。( 相同 x 的放在一起，若 x 相同則 y 較小的在前面，若 x、y 都相同則按照數值大小排序 ) 解題思路為了方便排序所以將 y 軸反轉，使用 map<pair<int, int>, priority_queue<int, vector<int>, greater<int>>> 紀錄資料，由於 map 的特性，會依照 pair 的 first 排序，所以裡面存放 {y, x}，由於 priority_queue 會依照資料的大小排序，所以用來存放數值。接著透過遞迴取得資料最後再存入 Vector 即可。 參考解法12345678910111213141516171819202122 ...

題目： LeetCode - 442. Find All Duplicates in an Array 題目說明給一個陣列 nums，1 ≤ nums[i] ≤ n。求此陣列中出現兩次的數字。※ 題目希望時間複雜度為 O(n)，且不使用額外的空間。 解題思路由於有 1 ≤ nums[i] ≤ n 這個條件，所以我們可以使用陣列元素的正負來判斷此數字是否出現過。具體作法為使用一個迴圈遍歷陣列，我們先判斷 nums[abs(nums[i]) - 1] 是否為負數，若為負數代表前面出現過，否則將 nums[abs(nums[i]) - 1] 設為負數。※ 使用 abs() 是為了避免這個元素已經被設為負數，減一是因為 nums[i] 的範圍為 [1, n]。 參考解法123456789101112131415161718192021// fast IOstatic auto __ = [](){ std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr ...

題目： LeetCode - 1535. Find the Winner of an Array Game 題目說明給一個陣列及一個整數 k，每次比對陣列前兩個數字，比較大的留著，較小的放到陣列尾端，求贏了 k 次的數。 解題思路其實放到尾端只是幌子，題目的答案其實只要遍歷一次陣列即可找到。定義一個 currMax 紀錄遍歷到目前的最大值，count 計算贏的次數，若 count 等於 k 就直接回傳 currMax，若遍歷完還沒回傳，代表 currMax 為最大值，直接回傳即可。 參考解法123456789101112131415161718192021// fast IOstatic auto __ = [](){ std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); return 0;}();class Solution {public: int getWinner(vector<int> ...