Leetcode刷題學習筆記 -- Greedy

# Leetcode刷題學習筆記 -- Greedy ## Introduce + 每次都把目前的狀態update到最佳狀態。 + 用哪種演法算可以得到題目的條件? ## Problems ### [376. Wiggle Subsequence](https://leetcode.com/problems/wiggle-subsequence/) ref : [Very-Simple-Java-Solution-With-detail-explanation](https://leetcode.com/problems/wiggle-subsequence/discuss/84849/Very-Simple-Java-Solution-with-detail-explanation) ```cpp= class Solution { enum state {up, down}; public: // why greedy? 每一次都把自己update到最佳解 int wiggleMaxLength(vector<int>& nums) { int sz = nums.size(); if(sz < 2) return sz; vector<int> vec; int start = 0; while(start + 1 < sz && nums[start + 1] == nums[start]) ++start; if(start == sz - 1) return 1; vec.push_back(nums[start]); vec.push_back(nums[start + 1]); int st = nums[start + 1] < nums[start]; for(int i = start + 2; i < sz; ++i) { if(st == up) { if(nums[i] < vec.back()) { vec.push_back(nums[i]); st = down; } else vec.back() = nums[i]; } else { // down if(nums[i] > vec.back()) { vec.push_back(nums[i]); st = up; } else vec.back() = nums[i]; } } // time : O(N) // space : O(N) return vec.size(); } }; ``` ### [45. Jump Game II](https://leetcode.com/problems/jump-game-ii/) 給你一個vector<int> nums，代表在i的時候每次可以跳躍的距離，請問最少次的跳躍可以達到終點。 > 1. 貪婪的想法，每次的跳躍，我都選最遠的跳躍距離。這樣到達終點就是最少的次數。例如: nums = [2,3,1,1,4] 當i = 0的時候，我只可以跳兩個距離。在i = 1時可以跳3，在i = 2時可以跳1，所以最遠可以跳到4。 > 2. 結束條件不是 i < sz? 因為當i == sz - 1時為終點不需要再跳，有可能重複計算一次 ```cpp= int jump(vector<int>& nums) { int sz = nums.size(); int farest = 0; int times = 0; int end = 0; // 上次最遠的距離 for(int i = 0; i < sz - 1; ++i) { farest = max(farest, i + nums[i]); // 目前可以跳到最遠的距離 if(end == i) { // times++; end = farest; } } // time : O(N) // space : O(1) return times; } ``` ### [621. Task Scheduler](https://leetcode.com/problems/task-scheduler/) 給你一個vector<char> tasks，CPU必須對這些task排程。但是相同的task必須間格n。試問最少需要多的時間。 > 1. Greedy標準的問法，求最大或是最小。 > 2. Greedy的想法，每次都依序取出頻率最大的task來處理。所以使用priority_queue來排序。 > 3. 因為有相同task必須間格n的限制，所以每次取出的task先暫時放在vector中，當vector的長度為n時，就可以把vector全部減一丟回priority_queue。 > 4. 最後判斷priority_queue是否為empty來增減ans。 ```cpp= // Greedy : 依序取出最頻率最大的task int leastInterval(vector<char>& tasks, int n) { if(n == 0) return tasks.size(); unordered_map<char, int> m; for(auto& t : tasks) m[t]++; priority_queue<int> pq; for(auto& it : m) pq.push(it.second); int ans = 0; while(!pq.empty()) { vector<int> next; int cnt = 0; for(int i = 0; i < n + 1; ++i) { if(pq.empty()) break; next.push_back(pq.top()); pq.pop(); cnt++; } // 先把next放回去。因為有可能不需要任何的task，所以必須先判斷 for(auto& nxt : next) { if(nxt == 1) continue; pq.push(nxt - 1); } // 如果pq是空的表示沒有任務則cnt, 還有新任次必須等待n ans += pq.empty() ? cnt : n + 1; } return ans; } ``` ### [2131. Longest Palindrome by Concatenating Two Letter Words](https://leetcode.com/problems/longest-palindrome-by-concatenating-two-letter-words/) 給你一個vector<string> words, 從words中拼出最長的palindrome。 > 1. 先對words做統計，並且判斷是對稱型還是反轉型。 > 2. 這邊的陷阱是中間可以放對稱型的。 > 3. 如果是偶數個就可以全放，如果是奇數個只能放偶數個。 > 4. 中間可以放一個對稱型的，所以使用center變數來表示。 > 5. 因為中間只需放一個，所以center使用OR。 ```cpp= // 常常都是special case來擾亂 // 反轉型的很好想，只取兩邊最少的 // 對稱型的只取偶數個，但是中間可以放一個，所以有center來表示。 int longestPalindrome(vector<string>& words) { unordered_map<string, int> m; for(auto& word : words) m[word]++; int ans = 0, center = 0; // center has only one symetric string for(auto& [w, cnt] : m) { string reverse = {w[1], w[0]}; if(w == reverse) { ans += cnt % 2 ? cnt - 1 : cnt; // 只取偶數 center |= cnt % 2; // 如果是奇數，取一個放在中央, 必須使用or避免被後來的修改 } else { if(m.count(reverse)) { ans += min(m[reverse], cnt); } } } return ans * 2 + (center ? 2 : 0); // time : O(N + N) = O(N) // space : O(N) } ``` ### [659. Split Array into Consecutive Subsequences](https://leetcode.com/problems/split-array-into-consecutive-subsequences/) 給你一個vector<int>，回傳是否可以把數列切割成一個或是數個consecutive subsequence。其中subsequence的條件是: 1. 長度必須大於等於3 2. 每個都是連續遞增的數 > 1. 這一題我是參考答案的。 > 2. 第一個疑問是為什麼是Greedy? > 這個題目是要分割成一個或是數個長度大於等於3的subsequence。 > case 1 : 如果沒重複數字，則一定是拼成一條最長的數列。 > case 2 : 如果有重複數字，則重複數字一定是其他subsequence的開頭。但是情況很多，因為下一個數字是要拚到那一個數列是個問題。當然要先滿足長度至少3的限制。 > 3. ==使用Greedy自行簡化題目。== > 第一條序列為最長的，因為如果沒重複的數字，則只會有一條數列。 > 盡可能的把第一條拼到最長，再來把第二條拼到最長,以此類推。 > 所以只會拼出最少數量的序列 ```cpp bool isPossible(vector<int>& nums) { unordered_map<int, int> freq, need; for(auto& n : nums) freq[n]++; for(auto& n : nums) { if(freq[n] == 0) continue; // 數字已經用完了 if(need[n] > 0) { // 可以合併到上一個序列 need[n]--; need[n + 1]++; // 繼續尋找下一個數字 } else if(freq[n + 1] > 0 && freq[n + 2] > 0) {// 可以當新的序列的起點 --freq[n + 1]; --freq[n + 2]; ++need[n + 3]; // 如果遇到n+3就合併到前一個序列 } else return false; --freq[n]; } // time : O(N + N) = O(N) // space : O(N + N) = O(N) return true; } ``` ### [1996. The Number of Weak Characters in the Game](https://leetcode.com/problems/the-number-of-weak-characters-in-the-game/) 給你一個vector<vector<int>> properties，有兩個屬性attack和defense。如果稱為weak是因為有同時attack和defense都比這個大的。回傳weak的個數。 > 1. 問題可以簡化成，如果比自己的attack還大的角色中，同時還有defense還比自己大的。那這個就是weak。 > 解法1 : > 先對attack排序，這樣只要往後比defense。 > 但是這種解法對attack一樣的情況不能解決。 > 所以defense必須從小排到大。 ```cpp= int numberOfWeakCharacters(vector<vector<int>>& properties) { sort(properties.begin(), properties.end(), [](vector<int>& a, vector<int>& b){ // 先對attack從大到小排序 if(a[0] > b[0]) return true; // 如果attack一樣就對defense從小大到排序 // 這樣的好處是當attack不一樣的時候， // defense是前一個attack中最大的。 else if(a[0] == b[0]) return a[1] < b[1]; else return false; }); // O(NlogN) int maxdef = INT_MIN; int ans = 0; for(auto& p : properties) { if(p[1] < maxdef) ans++; maxdef = max(maxdef, p[1]); } // O(N) return ans; } ``` | Time | Space | | -------- | -------- | | $O(NlogN + N) = O(NlogN)$| $O(1)$ | > 解法2 > 因為只需知道比自己大的attack中最大的defense，所以使用vector來記錄。 ```cpp= int numberOfWeakCharacters(vector<vector<int>>& ps) { // 紀錄每個attack中最大的defense vector<int> maxd(1e5 + 2); for(auto& p : ps) maxd[p[0]] = max(maxd[p[0]], p[1]); // O(N) // 紀錄每個大於這個attack中最大的defense for(int i = 1e5; i >= 1; --i) maxd[i] = max(maxd[i + 1], maxd[i]); int ans = 0; for(auto& p : ps) // O(N) ans += maxd[p[0] + 1] > p[1]; return ans; } ``` | Time | Space | | -------------------------- | ------------------ | | $O(N + 100001 + N) = O(N)$ | $O(100002) = O(1)$ | **因為space不會因為輸入vector長度改變** ### [334. Increasing Triplet Subsequence(Medium)](https://leetcode.com/problems/increasing-triplet-subsequence/description/) 找出index i < j < k，使用nums[i] < nums[j] < nums[k]。 > 1. 一開始用DP的方法結果TLE，因為time complexity $O(N^2)$ > 2. 這題的tag是greedy，就是每次都要取得最佳的local solution。 > 3. 因為是找出三個數值，然後越來越大，所以使用兩個變數first, second。 > 4. 當traversel整個vector的時候，每個n只會有三種情況。 > 5. 根據不同case，保留最小的數值來取代first或是second。 ```cpp= bool increasingTriplet(vector<int>& nums) { // only 3 case // case 1 : ----- first ----- second --n-- (n > second) // case 2 : ----- first --n-- second ----- (n > first && n < second), 用最小的取代second // case 3 : --n-- first ----- second ----- (n < first)，用最小的取代first int first = INT_MAX, second = INT_MAX; for(auto& n : nums) { if(n > second) return true; else if(n > first) second = n; else first = n; } // time : O(N) // space : O(1) return false; } ``` ### [1775. Equal Sum Arrays With Minimum Number of Operations](https://leetcode.com/problems/equal-sum-arrays-with-minimum-number-of-operations/description/) 給你兩個vector<int>，數值只有1~6，每次操作可以從任意element(1~6)跳到1~6，求最少次操作，可以把兩個vector的sum達到一樣。 [參考解答](https://leetcode.com/problems/equal-sum-arrays-with-minimum-number-of-operations/solutions/1086142/c-java-o-n/) > 1. 只能說 what a fucking good code. > 2. 貪婪點: 要最少次操作 --> 每次數值轉換都從最大或是最小下手。例如1->6 或是 6->1 可以一次減少5的總和差。 > 3. sum比較小的要往上跳，sum比較大的要往下跳。 > 4. 使用[priority_queue的解答](https://hackmd.io/m_6sQq4DS9u3TXsGYEcUTw#1775-Equal-Sum-Arrays-With-Minimum-Number-of-Operations) ```cpp= int minOperations(vector<int>& n1, vector<int>& n2) { if (min(n1.size() * 6, n2.size() * 6) < max(n1.size(), n2.size())) return -1; int sum1 = accumulate(begin(n1), end(n1), 0); int sum2 = accumulate(begin(n2), end(n2), 0); if (sum1 > sum2) swap(n1, n2); // sum小，sum大 int cnt[6] = {}, diff = abs(sum1 - sum2), res = 0; for (auto n : n1) // n1為sum小，所以往上跳 ++cnt[6 - n]; for (auto n : n2) // n2為sum大，所以往下跳 ++cnt[n - 1]; for (int i = 5; i > 0 && diff > 0; --i) { // 可以取的次數，取決於cnt[i]和 // diff可以取幾次的最小值 int take = min(cnt[i], diff / i + (diff % i != 0)); diff -= take * i; res += take; } return res; } ``` ### [134. Gas Station](https://leetcode.com/problems/gas-station/description/) > 1. 因為要繞一圈到起點，所以增加的gas一定要比減少的還要多，不然你從哪一個點出發，都繞不回起點。所以必須判斷sum使否大於等於0。 ```cpp= int sz = gas.size(), sum{0} for(int i = 0; i < sz; ++i) sum += gas[i] - cost[i]; return sum < 0 ? -1 : <start point>; ``` > 2. 假設從start出發，目前的gas為cur。如果走到了cur < 0表示從start這個點已經走不下去了。 > 3. 那從start到目前的中間點出發呢? 從start出發的gas-cost一定會大於0。因為小於0就會從下一個點出發，既然start點的gas-cost一定會大於，則中間點只會更小，所以更不可能達到目前的點，所以可以不用考慮。 ```cpp= int canCompleteCircuit(vector<int>& gas, vector<int>& cost) { int sz = gas.size(); int sum{0}, cur{0}, start{0}; for(int i = 0; i < sz; ++i) { sum += gas[i] - cost[i]; cur += gas[i] - cost[i]; if(cur < 0) { start = i + 1; cur = 0; } } return sum < 0 ? -1 : start; } ``` ### [1262. Greatest Sum Divisible by Three](https://leetcode.com/problems/greatest-sum-divisible-by-three/description/) 給你一個vector<int>，返回最大的element sum，可以被3整除。 > 1. Greedy的解法是，全部加起來後，看餘數是多少減掉餘數最小的值。 > 2. 紀錄每個餘數是1和2的前兩個最小值。 ```cpp= class Solution { public: int maxSumDivThree(vector<int>& nums) { vector<vector<int>> m(3, vector<int>(2, 1e5)); int sum{}; for(auto& n : nums) { sum += n; int r = n % 3; if(n < m[r][0]) { m[r][1] = m[r][0]; m[r][0] = n; } else if(n < m[r][1]) { m[r][1] = n; } } int r = sum % 3; if(r == 0) return sum; else if(r == 1) { if(m[1][0] == 1e5 && m[2][1] == 1e5) return 0; else return sum - min(m[1][0], m[2][0] + m[2][1]); } else { if(m[2][0] == 1e5 && m[1][1] == 1e5) return 0; else return sum - min(m[2][0], m[1][0] + m[1][1]); } } }; ``` ### [2178. Maximum Split of Positive Even Integers](https://leetcode.com/problems/maximum-split-of-positive-even-integers/description/) > 1. 一開始我使用backtrace結果TLE。 > 2. 參考答案之後，其實這題為Greedy題目。 > 3. 什麼情況會有最長結果? > 每次都取偶數的最小值。最後一個偶數在找可以組合成finalSum，就會得到最長的vector ```cpp= class Solution { public: vector<long long> maximumEvenSplit(long long finalSum) { if(finalSum % 2) return {}; vector<long long> ans; long long i = 2; long long curSum{}; while(i + curSum <= finalSum) { curSum += i; ans.push_back(i); i += 2; } ans.back() += finalSum - curSum; return ans; } }; ``` ### [435. Non-overlapping Intervals](https://leetcode.com/problems/non-overlapping-intervals/description/) 給你一些intervals，返回刪除最少的interval來達到non-overlap。 > 1. 一開始我使用dynamic programming結果TLE。 > 2. 參考官方答案，這邊使用greedy。 > 3. Greedy點是，如果當兩個interval overlap，我們要選擇哪一個? 當然是==選擇最早結束的那個，因為這樣之後可以選擇更多的interval。== ```cpp= class Solution { public: int eraseOverlapIntervals(vector<vector<int>>& intervals) { // O(NlogN) sort(intervals.begin(), intervals.end(), [](auto& a, auto& b){ return a[1] < b[1]; }); int ans = 0; int k = INT_MIN;// 前一個結束在INT_MIN for(int i = 0; i < intervals.size(); ++i) { // O(N) int x = intervals[i][0]; int y = intervals[i][1]; if(x >= k) k = y; else ans++; } return ans; // time : O(N + NlogN) = O(NlogN) // space : O(logN) sort function provided by STL } }; /* |--------| x = k 選擇越早結束的越好 |----------------| y |---------------| 下一個interval的start必須大於等於k 針對下一個interval會有兩種情況 case 1: | |------------| 沒有overlap，所以選擇此interval，並且更新k k x y case 2: |----|--------| k結束在interval中間，根據greedy原則，當overlap的時候 x k y 選擇最早結束的interval可以讓我們有更多interval的選擇。所以刪除此interval。 */ ``` ### [452. Minimum Number of Arrows to Burst Balloons](https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/description/) 這題和[435](/p9hSX0fpSQGwCUL3QF7cLA?both#435-Non-overlapping-Intervals)類似，改成數多少個non-overlap區域。 ```cpp= class Solution { public: int findMinArrowShots(vector<vector<int>>& points) { int sz = points.size(); // special case if(sz == 1) return 1; sort(points.begin(), points.end(), [](auto& a, auto& b){ return a[1] < b[1]; }); int ans = 1, cur = 0; for(int next = 1; next < sz; ++next) { if(points[cur][1] < points[next][0]) { // non-overlap, need one arrow ans++; cur = next; } } return ans; // time : O(NlogN + N) = O(NlogN) // space : O(logN) , because of sort() } }; ``` ### [1488. Avoid Flood in The City](https://leetcode.com/problems/avoid-flood-in-the-city/description/) 給你一個vector<int> rains，0:表示沒下雨可以選擇任一個lake把水抽掉，其他數值表示雨下在某個lake。連續兩次下在同一個lake就會洪水氾濫。 > 1. 參考[解答](https://leetcode.com/problems/avoid-flood-in-the-city/solutions/697840/c-o-nlogn-with-explanation/) > 2. 兩個相同數字中間，必須有0來抽掉水，不然就會氾濫。 > 3. Greedy點就是，必須找出最接近第一個數字的0來抽掉湖水。 ```cpp= // 1, ..., 1 // 則中間需要有0來抽掉 lake 1 的水 // 使用哪個0來抽掉水? Greedy: 最接近1的0，這樣其他0才可以保留給最多其他使用 class Solution { public: vector<int> avoidFlood(vector<int>& rains) { int sz = rains.size(); vector<int> rtn(sz, -1); set<int> zero; unordered_map<int, int> m; // lake, index : 紀錄每個lake最後index for(int i = 0; i < sz; ++i) { if(rains[i] == 0) { zero.insert(i); rtn[i] = 1; // default } else { if(m.count(rains[i])) { // 之前就有了，必須找出0抽掉水 auto it = zero.upper_bound(m[rains[i]]); if(it == zero.end()) return {}; // 找不到 rtn[*it] = rains[i]; zero.erase(*it); } m[rains[i]] = i; } } return rtn; } }; ``` ### [1353. Maximum Number of Events That Can Be Attended](https://leetcode.com/problems/maximum-number-of-events-that-can-be-attended/) > 1. 參考lee215的[解答](https://leetcode.com/problems/maximum-number-of-events-that-can-be-attended/solutions/510263/java-c-python-priority-queue/) > 2. Greedy點: 先結束的會議要先參加 > 3. 所以使用minheap來記錄每個先結束的會議。 ```cpp= class Solution { public: int maxEvents(vector<vector<int>>& events) { priority_queue<int, vector<int>, greater<int>> pq; //minheap, endtime 越早結束越早參加 sort(begin(events), end(events)); int i = 0, res = 0, n = events.size(); for(int d = 1; d <= 1e5; ++d) { while(pq.size() && pq.top() < d) // 會議已經結束，drop pq.pop(); while(i < n && events[i][0] == d) // 會議已經開始，加入pq pq.push(events[i++][1]); if(pq.size()) { // 因為一天只能加入一個會議，所以加入最早結束的會議 pq.pop(); ++res; } } return res; } }; ``` ###### tags: `leetcode` `刷題`

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.