Leetcode

433. Minimum Genetic Mutation Hardness: \(\color{orange}\textsf{Medium}\) Ralated Topics: Hash Table、String、Breadth-First Search 一、題目 A gene string can be represented by an 8-character long string, with choices from A, C, G, and T. Suppose we need to investigate a mutation from a gene string start to a gene string end where one mutation is defined as one single character changed in the gene string. For example, "AACCGGTT" --> "AACCGGTA" is one mutation. There is also a gene bank bank that records all the valid gene mutations. A gene must be in bank to make it a valid gene string. Given the two gene strings start and end and the gene bank bank, return the minimum number of mutations needed to mutate from start to end. If there is no such a mutation, return -1. Note that the starting point is assumed to be valid, so it might not be included in the bank. Example 1: ...

這一題的兩個關鍵點是 轉成角度，使用 atan2(dy, dx) 這個函式，並將 rad 轉成 degree。 要考慮座標 0 == 360，頭尾要相接。我的做法是將負數 +360 重覆放一遍。(或是只需要放小於 -180 + angle) 剩下的就是 sliding window 了。 class Solution { public: int visiblePoints(vector<vector<int>>& points, int angle, vector<int>& location) { vector<double> angles; int on = 0; for (const auto& p : points) { int dy = p[1] - location[1]; int dx = p[0] - location[0]; if (dx == 0 && dy == 0) { on++; continue; } double ang = atan2(dy, dx) * 180 / std::numbers::pi; if (ang < 180 + angle) angles.push_back(ang + 360); angles.push_back(ang); } sort(angles.begin(), angles.end()); int left = 0, right = 0, res = 0, n = angles.size(); while (right < n) { double curr = angles[right++]; while (curr - angles[left] > angle) left++; res = max(res, right - left); } return res + on; } };

這一題排序過後就變成簡單的不定長 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; } };