Leetcode

這一題排序過後就變成簡單的不定長 sliding window 了，但要注意處理 duplicated number class Solution { public: int minOperations(vector<int>& nums) { sort(nums.begin(), nums.end()); int left = 0, right = 0, n = nums.size(), res = 0; int curr = 0; while (right < n) { while (right < n - 1 && nums[right] == nums[right + 1]) right++; if (nums[right] - nums[left] > n-1) { while (left < n - 1 && nums[left] == nums[left + 1]) left++; left++; curr--; } right++; curr++; res = max(res, curr); } return n - curr; } };

這一題困難的部分在於計算 windows size 我的作法是根據 startPos + i 來計算左指針，左指針位置會在 startPos - max(k - 2*i, (k - i) / 2)，也就是算出左邊來回或是右邊來回兩種情況下， windowSize 最大的可能。 class Solution { public: int maxTotalFruits(vector<vector<int>>& fruits, int startPos, int k) { sort(fruits.begin(), fruits.end()); int curr = 0; int j = 0; while (j < fruits.size() && fruits[j][0] < startPos - k) j++; int u = j; for (int i = startPos - k; i <= startPos && j < fruits.size(); i++) { if (fruits[j][0] == i) curr += fruits[j++][1]; } if (j == fruits.size()) return curr; int res = curr; int left = startPos - k; for (int i = 1; i <= k && j < fruits.size(); i++) { int right = startPos + i; int pos = startPos - max(k - 2*i, (k - i)/2); if (fruits[j][0] == right) curr += fruits[j++][1]; while (left < pos) { if (fruits[u][0] == left++) curr -= fruits[u++][1]; } res = max(res, curr); } return res; } };

這一題的關鍵在於追縱離開 window 時的數字，可以滿足的最大值，所以可以用 dp + sliding window 來解這一題。 class Solution { public: int maximizeWin(vector<int>& nums, int k) { int n = nums.size(), left = 0, right = 0, res = 0; unordered_map<int,int> dp; int missed = 0; while (right < n) { while (right + 1 < n && nums[right] == nums[right+1]) right++; if (nums[right] - nums[left] > k) { while (nums[right] - nums[left] > k) { missed = max(missed, dp[nums[left++]]); } } dp[nums[right]] = right - left + 1; right++; res = max(res, right - left + missed); } return res; } };

這一題困難的部分在於計算 windows size 我的作法是根據 startPos + i 來計算左指針，左指針位置會在 startPos - max(k - 2*i, (k - i) / 2)，也就是算出左邊來回或是右邊來回兩種情況下， windowSize 最大的可能。 class Solution { public: int maxTotalFruits(vector<vector<int>>& fruits, int startPos, int k) { sort(fruits.begin(), fruits.end()); int curr = 0; int j = 0; while (j < fruits.size() && fruits[j][0] < startPos - k) j++; int u = j; for (int i = startPos - k; i <= startPos && j < fruits.size(); i++) { if (fruits[j][0] == i) curr += fruits[j++][1]; } if (j == fruits.size()) return curr; int res = curr; int left = startPos - k; for (int i = 1; i <= k && j < fruits.size(); i++) { int right = startPos + i; int pos = startPos - max(k - 2*i, (k - i)/2); if (fruits[j][0] == right) curr += fruits[j++][1]; while (left < pos) { if (fruits[u][0] == left++) curr -= fruits[u++][1]; } res = max(res, curr); } return res; } };

這一題是求 maxcnt 而不是求 window size condition 是 window_size - maxcnt > k 接著套不定長 sliding window。 class Solution { public: int longestEqualSubarray(vector<int>& nums, int k) { int res = 0, left = 0, right = 0, n = nums.size(); int maxcnt = 0; unordered_map<int,int> cnt; while (right < n) { int num = nums[right++]; maxcnt = max(maxcnt, ++cnt[num]); while (right-left-maxcnt > k) cnt[nums[left++]]--; res = max(res, maxcnt); } return res; } };

這題同樣是經典的 sliding window，可參考 1658，同樣是頭尾求最短轉換成求最長 window 的題型。 接著套不定長 sliding window。 class Solution { public: int takeCharacters(string s, int k) { // 先檢驗題目本身有沒有可能符合，因為 s 至少要 3 * k 才可能有解 int need = k * 3; int n = s.size(); if (n < need) return -1; int cnt[3]; memset(cnt, 0, sizeof(cnt)); for (const auto& c : s) { cnt[c-'a']++; } // 檢查各字元是否至少有 k 個 for (int i = 0; i < 3; i++) { if (cnt[i] < k) return -1; cnt[i] -= k; } // 如果都符合，字串長度又剛好等於 need，那必定是整個 string 都需要 if (n == need) return n; // 剩下的就是經典的 sliding window，滑起來就是了 int left = 0, right = 0, res = 0; int curr[3]; memset(curr, 0, sizeof(curr)); while (right < n) { char c = s[right++]; curr[c-'a']++; while (curr[c-'a'] > cnt[c-'a']) { curr[s[left++]-'a']--; } res = max(res, right-left); } // 注意要還原 return n - res; } };

這一是經典的頭尾相連問題，可以透過透過以下手法換轉成簡單的 sliding window find head + tail = x let head + body + tail == total the problem becomes FIND body = total - x，問題從求最短頭+尾 變成 最長 window 套不定長 sliding window。 class Solution { public: int minOperations(vector<int>& nums, int x) { int total = accumulate(nums.begin(), nums.end(), 0); int target = total - x; int left = 0, right = 0, res = -1, n = nums.size(); int curr = 0; if (target == 0) res = 0; // 注意要處理 boundary condition while (right < n) { curr += nums[right++]; while (curr > target && left < right) { curr -= nums[left++]; } if (curr == target) { res = max(res, right-left); } } return res == -1 ? -1 : n - res; // 最後要將長度轉回來 } };

這題同樣是經典的 sliding window，經排序過後，我們可以透過 len * max_element_in_window - accumulate_in_window 的方式來求 token need， 接著套不定長 sliding window。 class Solution { public: int maxFrequency(vector<int>& nums, int k) { sort(nums.begin(), nums.end()); int left = 0, right = 0, res = 0, n = nums.size(); long long curr = 0; while (right < n) { int num = nums[right++]; curr += num; while ((long long)(right-left) * num - curr > k) { curr -= nums[left++]; } res = max(res, right-left); } return res; } };

簡單的不定長 sliding window 問題。 class Solution { public: int longestOnes(vector<int>& nums, int k) { int res = 0, left = 0, right = 0, n = nums.size(); int curr = 0; int cnt = 0; while (right < n) { int num = nums[right++]; while (cnt == k && num == 0) { if (nums[left++] == 0) cnt--; } if (num == 0) cnt++; res = max(res, right-left); } return res; } };

簡單的不定長 sliding window 問題, 正反各做一遍即可。 class Solution { private: int maxConsecutiveAnswersWith(string keys, int k, char c) { int left = 0, right = 0, res = 0, n = keys.size(); int cnt = 0; while (right < n) { char key = keys[right++]; while (key == c && cnt == k) { if (keys[left++] == c) { cnt--; } } if (key == c) cnt++; res = max(res, right-left); } return res; } public: int maxConsecutiveAnswers(string answerKey, int k) { return max(maxConsecutiveAnswersWith(answerKey, k, 'T'), maxConsecutiveAnswersWith(answerKey, k, 'F')); } };