發表文章

目前顯示的是 1月, 2021的文章

C++ 中 std::lock_guard 與 std::unique_lock 的區別

C++ 11 中新增了二個處理 lock 的 wrapper,分別是 std::lock_guard 以及 std::unique_lock, 我們首先來看 C++ 11 對 std::lock_guard 的實作:  template<class _Mutex> class lock_guard<_Mutex> { // specialization for a single mutex public: typedef _Mutex mutex_type; explicit lock_guard(_Mutex& _Mtx) : _MyMutex(_Mtx) { // construct and lock _MyMutex.lock(); } lock_guard(_Mutex& _Mtx, adopt_lock_t) : _MyMutex(_Mtx) { // construct but don't lock } ~lock_guard() _NOEXCEPT { // unlock _MyMutex.unlock(); } lock_guard(const lock_guard&) = delete; lock_guard& operator=(const lock_guard&) = delete; private: _Mutex& _MyMutex; }; 從程式碼中,可以看到其主要就是在建構子中上鎖,並於解構子中解鎖, 因此 lock_guard 是一個非常輕量的 wrapper,只提供於 block 自動上鎖與解鎖 (避免開發者忘記)  接著我們再來看 std::unique_lock,根據 cppreference 的描述: The class unique_lock is a general-purpose mutex ownership wrapper allowing deferred locking, time-constrained attempts at locking, recursive locking, transfer of lock ownership, and u

[LeetCode][Hard] 123. Best Time to Buy and Sell Stock III

Leetcode 網址: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/ 題目說明: 給定一個長度為 n 的序列,序列內的第 i 個數字代表第 i 天股票 A 的價格, 投資人被允許這 n 天內最多執行 2 次完成的交易 (買進 + 賣出算一次完整的交易), 請設計一個演算法找出最大的獲利。 Note: 交易所限制買進時,手上必須沒有股票。 Example 1: Input: prices = [3,3,5,0,0,3,1,4] Output: 6 Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3. Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3. Example 2: Input: prices = [1,2,3,4,5] Output: 4 Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4. Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again. 解題說明: 遇到這種題目一開始沒有想法的話就先將 input 變小, 例如思考長度為 n 的序列之最大獲利要如何從 n - 1 中的序列推出呢 ? 思考了之後可以發現長度為 n 的序列之最大獲利可以分成二個情況: 1. 最大獲利的交易是否包含第 n 天 ? 如果不包含那答案就跟 n - 1 序列的最大獲利相同 2. 最大的獲利交易包含第 n 天,那麼我們就從 n - 1 的序列中找出最便宜的價格買進,並於第 n 天賣出 有以上的想法就可以把這想法寫成演算法囉 ~ 程式碼 class Solution { pu

[LeetCode][Hard] 72. Edit Distance

圖片
Leetcode 網址: https://leetcode.com/problems/edit-distance/ 題目說明: 給定二個字串 word1 以及 word2,請找出最少需要幾個操作才能將將 word1 轉換成 word2。 操作的定義有三種:    1. 新增字元 2. 刪除字元 3. 取代字元 Example 1: Input: word1 = "horse", word2 = "ros" Output: 3 Explanation: horse -> rorse (replace 'h' with 'r') rorse -> rose (remove 'r') rose -> ros (remove 'e') 解題說明: 遇到這種題目一開始沒有想法的話就先將 input 變小, 以範例 1 的而言,我們慢慢將 input 由小至大就可以推論出下表: 最後根據上表及推導中可以發現這題是個 Dynamic Programming 題型, 將推導的結果寫成演算法即可解決此題。 程式碼 class Solution { public: int minDistance(string word1, string word2) { int dp[word1.length() + 1][word2.length() + 1]; memset(&dp[0][0], 0, (word1.length() + 1) * (word2.length() + 1) * sizeof(int)); for (int i = 1; i <= word1.length(); i++) dp[i][0] = i; for (int i = 1; i <= word2.length(); i++) dp[0][i] = i; for (int i = 1; i <= word1.length(); i++) { for (int j = 1; j <= word2.length(); j++)

[LeetCode][Hard] 76. Minimum Window Substring

Leetcode 網址: https://leetcode.com/problems/minimum-window-substring/ 題目說明: 給定一個字串 s 以及一個字串序列 t, 請在字串 s 中找出包含所有 t 出現的字元所需要的最短字串長度。 備註: 題目保證最短字串長度會是 unique 的。 Example 1: Input: s = "ADOBECODEBANC", t = "ABC" Output: "BANC" Example 2: Input: s = "a", t = "a" Output: "a" 解題說明: 觀察題目敘述很直覺可以發現是 Sliding Window 的題目, 我們觀察 Example 看如何先找出單一個包含字串 t 的答案 (先不管最短) ~ 1. 訪問 A 發現 A 是需要的字元,由於是第一個出現的需要字元所以 start 紀錄成 0;需要字元剩餘 2 2. 訪問 D 發現 D 不是需要的字元,繼續往下走;需要字元剩餘 2 3. 訪問 O 發現 O 不是需要的字元,繼續往下走;需要字元剩餘 2 4.  訪問 B 發現 B 是需要的字元,由於還欠缺其他字元所以繼續往下走;需要字元剩餘 1 5. 訪問 E 發現 E 不是需要的字元,繼續往下走;需要字元剩餘 1 6. 訪問 C 發現 C 是需要的字元,找到所有字元所以記錄這個答案 ADOBEC 以上是找出非最短的算法,接著我們要思考如何從這組算法找出下一組答案 ~ 很直覺可以發現若找出一組比 ADOBEC 更短的答案,那勢必得捨去 A (也就是移除字串 ADO), 所以捨去 ADO 之後將 Start 設成下一個需要的字元 B (index = 3), 又由於我們只有捨棄 A,所以只要從 C 開始往後找找出下一個 A 就會是下一組可能更短的答案, 將以上的想法寫成 for loop 並判斷長度就可以找出答案了。 程式碼 class Solution { public: string minWindow(string s, string t) { int minStart = 0, minLength = 0;

[LeetCode][Hard] 239. Sliding Window Maximum

圖片
Leetcode 網址: https://leetcode.com/problems/sliding-window-maximum/ 題目說明: 給定一個沒有排列長度為 n 的陣列與窗口大小 k ( 1 <=k <= n), 每次窗口會往右移動一格,直到窗口大小超出陣列長度, 請找出移動過程中窗口範圍內的最大值。 解題說明: 這題最暴力法直接做就是每次從大小為 k 窗口中找最大元素, 由於 n 可能等於 n / 2,所以暴力法的時間複雜度為 O (n^2)。 接著再來思考比較好的做法就是 Max Heap, Max Heap 插入跟刪除的時間複雜度皆為 O (log n), 由於插入跟刪除最多為 n 次,所以其時間複雜度可以壓到 O (n log n) ~ 後來解完題目後,看了下討論區有種 O (n) 的解法是用 double-ended queue, 其算法概念是每次新增元素到 queue 前,把那些沒有用的元素先 pop 掉, 例如: 4 3 2 1 7 來說,當我們要新增 7 的時候就把前面的 pop 掉, 原因是往右邊移動的話, 4 3 2 1 這幾個數字絕對不可能是最大值, 所以有以上想法後就可以解決此題啦! 程式碼 (Max Heap) class Solution { public: vector<int> maxSlidingWindow(vector<int>& nums, int k) { vector<int> result; priority_queue<pair<int, int>> pq; for (int i = 0; i < nums.size(); i++) { while (i >= k && pq.size() > 0 && i - k >= pq.top().second) pq.pop(); pq.push(pair(nums[i], i)); if (i >= k - 1) result.push_back(pq.top().first);

[LeetCode][Hard] 154. Find Minimum in Rotated Sorted Array II

Leetcode 網址: https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/ 題目說明: 這題跟 153 一樣差別在於 153 保證不會有重複的元素,但 154 可能有重複的元素。 解題說明: 由於是否重複對於我們 153 的解法並無影響,所以直接套用 153 的程式即可解決此題。 程式碼 class Solution { public: int findMin(vector<int>& nums) { for (int i = 0, maxNum = INT_MIN; i < nums.size(); i++) { if (nums[i] >= maxNum) maxNum = nums[i]; else return nums[i]; } return nums[0]; } }; 結果 Runtime:  4 ms , faster than  98.88%  of C++ online submissions for  Find Minimum in Rotated Sorted Array II. Memory Usage:  12.2 MB , less than  96.69%  of C++ online submissions for  Find Minimum in Rotated Sorted Array II.

[LeetCode][Medium] 153. Find Minimum in Rotated Sorted Array

Leetcode 網址: https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/ 題目說明: 給一個長度為 n 的已排序並 rotate 過 1 ~ n 次的陣列,請找出這個陣列中最小的數值。 Rotate 範例: 原始已排序陣列: [0,1,2,4,5,6,7] 經過 1 次 rotate => [7,0,1,2,3,4,5,6] 經過 2 次 rotate => [6,7,0,1,2,3,4,5] 經過 3 次 rotate => [5,6,7,0,1,2,3,4] ... 經過 7 次 rotate => [0,1,2,3,4,5,6,7] Example 1: Input: nums = [3,4,5,1,2] Output: 1 Explanation: The original array was [1,2,3,4,5] rotated 3 times. Example 2: Input: nums = [4,5,6,7,0,1,2] Output: 0 Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times. Example 3: Input: nums = [11,13,15,17] Output: 11 Explanation: The original array was [11,13,15,17] and it was rotated 4 times.   解題說明: 觀察範例可以發現, rotate 1 次代表第 1 ~ 1 個元素會為第 n 大到第 n 大,第 2 個元素為最小 rotate 2 次代表第 1 ~ 2 個元素會為第 n - 1 大到第 n 大,第 3 個元素為最小 rotate 3 次代表第 1 ~ 3 個元素會為第 n - 2 大到第 n 大,第 4 個元素為最小 ... rotate n 次代表第 1 ~ n 個元素會為第 1 大到第 n 大,第 n 個元素為最小 以此邏輯即可以寫出非常簡單的算法囉 ~ 程式碼 class Solution { public: int findM

[LeetCode][Hard] 128. Longest Consecutive Sequence

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][Medium] 1079. Letter Tile Possibilities

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][Medium] 988. Smallest String Starting From Leaf

圖片
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][Medium] 959. Regions Cut By Slashes

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][Medium] 1254. Number of Closed Islands

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 來操作字串, 然而很多 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 裡面實際訪問的是