AMGE’s Blogger

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 網址: 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); ...