發表文章

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 o...

[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 f...