AMGE’s Blogger

Leetcode 網址: https://leetcode.com/problems/longest-consecutive-sequence/ 題目說明: 給定一個沒有排列的陣列，找出最長的連續序列長度。 Follow up: 你能否在 O(n) 時間內完成呢? Example 1: Input: nums = [100,4,200,1,3,2] Output: 4 Explanation: The longest consecutive elements sequence is [1, 2, 3, 4] . Therefore its length is 4. Example 2: Input: nums = [0,3,7,2,5,8,4,6,0,1] Output: 9   解題說明: 由於題目要求的是 O(n) 時間，也就是說可以直接捨棄排序法了， 因為比較排序的排序法時間複雜度為 O( n log n) ~ 所以很直覺出題者應該是想要我們使用額外的空間來處理問題。 所以我們直接把 nums 轉成 unordered_map， 以範例 1 而言就是 m[100] = 1, m[4] = 1, m[200] = 1, ..., m[2] = 1， 由於 unordered_map 訪問的平均時間為 O(1)，所以轉換過成只需要 O(n)， 接著直接對這些 map 中存在的元素做 traverse 紀錄長度，就可以找出答案了 ~ 程式碼 class Solution { public: int traverse(unordered_map<int, int>& m, int index, int offset, int value) { if (m.find(index + offset) != m.end()) { m[index + offset] = traverse(m, index + offset, offset, value + 1); return m[index + offset]; } return value; } int longestConsecutive(vector...

Leetcode 網址: https://leetcode.com/problems/letter-tile-possibilities/ 題目說明: 給定一個長度 1 到長度 7 的大寫英文字串， 請問用這些字串可以組出不為空的序列有幾組？ 解題說明: 這題很顯然是排列組合的問題， 由於題目給定的是一個字串，因此我們需要先把字串轉換成"字母的數量"， 接著就直接透遞迴去算排列組合就能得到答案了 ~ 程式碼 class Solution { public: int numTilePossibilities(string tiles, int n = 0) { int m[26] = {0}; for (int i = 0; i < tiles.length(); i++) m[tiles[i] - 'A']++; return recursive(m, n); } int recursive(int* m, int& n) { for(int i = 0; i < 26; i++) { if (!m[i]) continue; m[i]--, n++; recursive(m, n); m[i]++; } return n; } }; 結果 Runtime:  0 ms , faster than  100.00%  of C++ online submissions for  Letter Tile Possibilities. Memory Usage:  5.9 MB , less than  100.00%  of C++ online submissions for  Letter Tile Possibilities.

Leetcode 網址: https://leetcode.com/problems/smallest-string-starting-from-leaf/ 題目說明: 給定一個 Binary Tree，從這個 Binary Tree 中找出從 Leaf 到 Root 最小的單字 (最小的單字意味者字典排序， a -> z，短到長) 解題說明: 這題很直觀，就是直接從 Binary Tree 的 Root 訪問到 Leaf， 最後到 Leaf 之後再去依照字典排序比較要保留哪個單字， 途中保存 Node 的方式可以使用 vector ，亦或者是使用 string， 由於只需要訪問所有的 Node，所以這題的時間複雜度是 O (n)， 而因為我們始終只保留最短的單字，所以空間複雜度是 O (n)。 程式碼 class Solution { public: string answer; string smallestFromLeaf(TreeNode* root) { answer = ""; vector<int> nodes; if (root) traverseTree(root, nodes); return answer; } void updateAnswer(vector<int>& nodes) { bool flag = true; int length = answer.length(); for (int i = nodes.size() - 1, j = 0; i >= 0 && j < length && flag; i--, j++) { if (nodes[i] < (answer[j] - 'a')) break; if (nodes[i] > (answer[j] - 'a')) flag = false; } if (flag) { a...

Leetcode 網址: https://leetcode.com/problems/regions-cut-by-slashes/ 題目說明: 這題跟 LeetCode 1254 非常像，給定 Grid 以及其邊線， 要找尋這些邊線切出來的 Region 總共有幾塊。 解題說明: 因為是找 Region 數量問題，所以方向很直覺就是藉由 DFS 去訪問， 不過這題比較不同的是，他給你的 Grid 是包含 "邊線" 而非 "'障礙物"， 意思也就是追要把這個 Grid 先轉換成 DFS 能 Traverse 的 Grid， 觀察題目給的幾個範例後，一開始想說把 Grid 放大成二倍， 結果遇到這個情況會過不了: ["//", "/ "]， 放大 2 倍的 Grid: 01 0 1 1010 0100 1000 也就是說，因為只有 2 倍大的 Grid 空間不夠，進而造成連續二個 // 形成一個不存在的 region， 所以發現問題之後，嘗試改成 3 倍大確認跟預期的 Grid 無誤後 Submit 即 AC 了。 放大 3 倍的 Grid: 001001 010010 100100 001000 010000 100000 程式碼 class Solution { public: int count; void traverseIsland(vector<vector<int>>& grid, int x, int y) { if (y < 0 || x < 0 || y >= grid.size() || x >= grid[0].size()) return; if (grid[y][x]) return; grid[y][x] = count; traverseIsland(grid, x - 1, y); traverseIsland(grid, x + 1, y); traverseIsland(grid, x, y - 1); return traverseIsland(gri...

Leetcode 網址: https://leetcode.com/problems/number-of-closed-islands/ 題目說明: 題目大意是要從一個二維地圖中，找出所有"完全被海包圍的陸地"， 如果陸地在地圖邊界，則不算 "完全被海包圍的陸地"。 解題說明: 這題很直覺，我們就是直接藉由 DFS 去訪問那些陸地， 如果訪問陸地途中碰到邊界，則代表該陸地沒有完全被海包圍， 如果訪問完連續的陸地也沒碰到邊界，則代表該陸地有完全被海包圍。 程式碼 class Solution { public: bool traverseIsland(vector<vector<int>>& grid, int x, int y) { if (y < 0 || x < 0 || y >= grid.size() || x >= grid[0].size()) return false; if (grid[y][x]) return true; grid[y][x] = 1; bool isClosedIsland = traverseIsland(grid, x - 1, y); isClosedIsland = isClosedIsland & traverseIsland(grid, x + 1, y); isClosedIsland = isClosedIsland & traverseIsland(grid, x, y - 1); return isClosedIsland & traverseIsland(grid, x, y + 1); } int closedIsland(vector<vector<int>>& grid) { int count = 0, width = grid[0].size(), height = grid.size(); for (int i = 0; i < height; i++) ...

開發 MFC 視窗程式時，很常會使用到 CString 來操作字串， 然而很多 MFC 的初學者雖然會使用 CString，但卻對於 CString 有很多疑問， 以下是我針對初學者對於 CString 最常見的三個問題之說明 ~ Q. 在一個 function 裡宣告 CString 變數，這個變數是儲存在 Stack 還是 Heap ? 一個變數儲存在哪裡取決於這個變數的宣告方式， 如果一個變數是全域變數或 static 變數，那這個變數是儲存在 data， 如果一個變數是區域變數，那這個變數是儲存 stack， 如果一個變數是藉由執行時 new/malloc 產生，那這個變數是儲存 heap。 CString 也不例外，一樣會 follow 以上的規則。 Q. CString str = _T("1111111111"); sizeof(str) 是多大呢? sizeof(CString) 呢? sizeof(CString *) 呢? 這題是很多 MFC 初學者會回答錯的事情，最常聽到的錯誤答案是字串多大 CString 就多大。 回答這個問題之前，我們必須要清楚的知道 CString 是一個 Class， 而一個 Class 的大小取決於這個 Class 的 member data， 因此 CString 也不例外，CString 的大小取決於 CString 的 member data， 而 CString 的 member data 只有 PXSTR m_pszData， 所以 sizeof(str) = sizeof(CString) = sizeof(m_pszData) => 32 位元答案是 4, 64 位答案則是 8 sizeof(CString *) => 32 位元答案是 4, 64 位答案則是 8。 Q. 一個 Function 的參數中有 CString，它會如何傳遞？ 先來幫大家複習一下 C++傳遞參數的三種方法，CString 也是一樣藉由這三種方式傳遞。 1. Pass by value (Call by value) => void function(CString str); 這一種方式會在傳遞參數之前建立一份 Copy 的 CString， 所以在 function ...

最近在公司發現一個小問題， 當我們在 Debug Process A 的時候 (Process A 處於 break mode)， 如果我們在其它 Process B 例如: Chrome、記事本有打字的話，Process B 會直接 hang 住。 而造成這個現象的原因是來自於公司之前有人為了做熱鍵功能， 因此使用 SetWindowsHookEx hook global keyboard event。 但是由於 Process A 在 break mode，所以 OS 沒辦法將 keyboard event 交給 Process A 處理， 因此 OS 只能 suspend Process B 直到 keyboard event 被 Process A 處理完成。 補充說明一下：以上是 Windows 10 針對 SetWindowsHookEx 行為，不同版本可能有不同行為。 例如: 在 Windows 7 則是會將 DLL Inject 到其它 Process ， 但因為 Windows 7 有 64 位元的版本，所以 DLL 可能會有位元相容性問題， 針對不能相容的 DLL，Windows 7 行為跟 Windows 10 相同 (Context switch 回 Process A)， 至於能相容的 Process 則不需要 Context switch (所以也不會有卡住的問題)。 了解整個來龍去脈後，要解決問題就簡單了， 第一種就是在編譯 Debug 版本不  hook global keyboard event (workaround)， 第二種就是改用  RegisterHotKey 處理熱鍵 ， 第二種才是比較好的解法， 因為熱鍵而要  hook global keyboard event 非常不合理 (有資安上疑慮)， 且其行為一般會被防毒軟體視為惡意軟體， 因此大家要做熱鍵功能還是乖乖使用  RegisterHotKey  吧 ~