📝前言說明：

• 本專欄主要記錄本人的貪心算法學習以及LeetCode刷題記錄，按專題劃分
• 每題主要記錄：（1）本人解法 + 本人屎山代碼；（2）優質解法 + 優質代碼；（3）精益求精，更好的解法和獨特的思想（如果有的話）；（4）貪心策略正確性的 “證明”
• 文章中的理解僅為個人理解。如有錯誤，感謝糾錯

🎬個人簡介：努力學習ing
📋本專欄：C++刷題專欄
📋其他專欄：C語言入門基礎，python入門基礎，C++學習筆記，Linux
🎀CSDN主頁 愚潤澤

你可以點擊下方鏈接，進行其他貪心算法題目的學習

點擊鏈接	開始學習
貪心day1	貪心day2
貪心day3	貪心day4
貪心day5	貪心day6
貪心day7	貪心day8
貪心day9	貪心day10

也可以點擊下面連接，學習其他算法

點擊鏈接	開始學習
優選專題	動態規劃
遞歸、搜索與回溯	貪心算法

題單獲取→ 【貪心算法】題單匯總

---

452. 用最少數量的箭引爆氣球

題目鏈接：https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/description/

個人解

思路：

• 和前面的題目差不多

屎山代碼：

class Solution {
public:int findMinArrowShots(vector<vector<int>>& points) {// 同樣是合并區間，如果有重疊部分，則只需要一支箭// 按照右端點排序，我們射箭的時候往氣球的結束位置射更容易射中多個(貪心)int ans = 1, n = points.size(); // 第一個始終要一箭ranges::sort(points.begin(), points.end(), [&](vector<int>& p1, vector<int>& p2){return p1[1] < p2[1];});int left = points[0][0], right = points[0][1];for(int i = 1; i < n; i++){if(points[i][0] > right)  // 射前一個氣球的時候不能射到后一個氣球，要加箭{ans++;right = points[i][1];  // 更新下一只箭射的位置}}return ans;}
};

時間復雜度：$O(nlogn)$
空間復雜度：$O(logn)$

---

397. 整數替換

題目鏈接：https://leetcode.cn/problems/integer-replacement/description/

---

優質解

遞歸 + 記憶化搜索

代碼：

class Solution {
private:unordered_map<long long, int> memo;int dfs(long long n) {  // 用long long避免溢出if (n == 1) return 0;if (memo.count(n)) return memo[n];int steps;if (n % 2 == 0) {steps = 1 + dfs(n / 2);} else {// 對于奇數，分別處理n-1和n+1的情況steps = 1 + min(dfs(n - 1), dfs(n + 1));}memo[n] = steps;return steps;}public:int integerReplacement(int n) {return dfs((long long)n);  // 轉換為long long再處理}
};

時間復雜度：$O(logn)$
空間復雜度：$O(logn)$

貪心

• 我們把每個數寫成二進制的方式進行分析，同時/操作，變成二進制右移一位
• 然后通過找局部最優解，發現"貪”的方法
  
  代碼：

class Solution {
public:int integerReplacement(long long n) {int ans = 0;while(n != 1){if (n % 2 == 0)n /= 2;else{if(n == 3 || (n & 3) == 1)n -= 1;elsen += 1;}ans++;}return ans;}
};

---

354. 俄羅斯套娃信封問題

題目鏈接：https://leetcode.cn/problems/russian-doll-envelopes/description/

---

優質解

解法一（動態規劃）

思路：

• 按左端點排序，此時只需要關注右端點
• 因為要套娃 → 變成求最長遞增子序列問題（按右端點）

代碼：

class Solution {
public:int maxEnvelopes(vector<vector<int>>& env) {int n = env.size();ranges::sort(env);vector<int> dp(n, 1);int ans = 1;for(int i = 1; i < n; i++){for(int j = 0; j < i; j++){if(env[j][1] < env[i][1] && env[j][0] < env[i][0]) // 因為會出現相同的左端點dp[i] = max(dp[j] + 1, dp[i]);}ans = max(ans, dp[i]);}return ans;}
};

時間復雜度：$O(n^2)$，會超時

解法二（貪心）

• 解法：重寫排序 + 貪心 + 二分
  因為本題需要考慮兩個端點，所以需要重寫排序（減少貪心時的分類討論）
• 排序：左端點從小到大排，左端點相同時，右端點從大到小的順序排 → 變成完全的最長遞增子序列
• 然后用貪心 + 二分的方式解決問題

代碼：

class Solution {
public:int maxEnvelopes(vector<vector<int>>& env) {int n = env.size();sort(env.begin(), env.end(), [&](vector<int> &a, vector<int> &b){return a[0] != b[0] ? a[0] < b[0] : a[1] > b[1];});vector<int> ret; // 存儲最長子序列ret.push_back(env[0][1]);for(int i = 1; i < n; i++){int b = env[i][1];if(b > ret.back()) ret.push_back(b);else{int left = 0, right = ret.size() - 1;while(left < right){// 找到第一個 > b 的數int mid = (left + right) >> 1;if(ret[mid] < b) left = mid + 1; // <=b 可以全部排除else right = mid;}ret[left] = b;}}return ret.size();}
};

時間復雜度：$O(nlogn)$

---

🌈我的分享也就到此結束啦🌈
要是我的分享也能對你的學習起到幫助，那簡直是太酷啦！
若有不足，還請大家多多指正，我們一起學習交流！
📢公主，王子：點贊👍→收藏?→關注🔍
感謝大家的觀看和支持！祝大家都能得償所愿，天天開心！！！