【贪心算法】day9

📝前言说明：

• 本专栏主要记录本人的贪心算法学习以及LeetCode刷题记录，按专题划分
• 每题主要记录：（1）本人解法 + 本人屎山代码；（2）优质解法 + 优质代码；（3）精益求精，更好的解法和独特的思想（如果有的话）；（4）贪心策略正确性的 “证明”
• 文章中的理解仅为个人理解。如有错误，感谢纠错

🎬个人简介：努力学习ing
📋本专栏：C++刷题专栏
📋其他专栏：C语言入门基础，python入门基础，C++学习笔记，Linux
🎀ZEEKLOG主页 愚润泽

你可以点击下方链接，进行其他贪心算法题目的学习

也可以点击下面连接，学习其他算法

题单获取→ 【贪心算法】题单汇总

题目

• 452. 用最少数量的箭引爆气球
  • 个人解
• 397. 整数替换
  • 优质解
    • 递归 + 记忆化搜索
    • 贪心
• 354. 俄罗斯套娃信封问题
  • 优质解
    • 解法一（动态规划）
    • 解法二（贪心）

452. 用最少数量的箭引爆气球

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

个人解

思路：

• 和前面的题目差不多

屎山代码：

classSolution{public:intfindMinArrowShots(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 ( n l o g n ) O(nlogn) O(nlogn)
空间复杂度： O ( l o g n ) O(logn) O(logn)

397. 整数替换

题目链接：https://leetcode.cn/problems/integer-replacement/description/

优质解

递归 + 记忆化搜索

代码：

classSolution{private: unordered_map<longlong,int> memo;intdfs(longlong n){// 用long long避免溢出if(n ==1)return0;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:intintegerReplacement(int n){returndfs((longlong)n);// 转换为long long再处理}};

时间复杂度： O ( l o g n ) O(logn) O(logn)
空间复杂度： O ( l o g n ) O(logn) O(logn)

贪心

• 我们把每个数写成二进制的方式进行分析，同时/操作，变成二进制右移一位

然后通过找局部最优解，发现"贪”的方法

代码：

classSolution{public:intintegerReplacement(longlong n){int ans =0;while(n !=1){if(n %2==0) n /=2;else{if(n ==3||(n &3)==1) n -=1;else n +=1;} ans++;}return ans;}};

354. 俄罗斯套娃信封问题

题目链接：https://leetcode.cn/problems/russian-doll-envelopes/description/

优质解

解法一（动态规划）

思路：

• 按左端点排序，此时只需要关注右端点
• 因为要套娃 → 变成求最长递增子序列问题（按右端点）

代码：

classSolution{public:intmaxEnvelopes(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 ) O(n^2) O(n2)，会超时

解法二（贪心）

• 解法：重写排序 + 贪心 + 二分
  因为本题需要考虑两个端点，所以需要重写排序（减少贪心时的分类讨论）
• 排序：左端点从小到大排，左端点相同时，右端点从大到小的顺序排 → 变成完全的最长递增子序列
• 然后用贪心 + 二分的方式解决问题

代码：

classSolution{public:intmaxEnvelopes(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 ( n l o g n ) O(nlogn) O(nlogn)

🌈我的分享也就到此结束啦🌈
要是我的分享也能对你的学习起到帮助，那简直是太酷啦！
若有不足，还请大家多多指正，我们一起学习交流！
📢公主，王子：点赞👍→收藏⭐→关注🔍
感谢大家的观看和支持！祝大家都能得偿所愿，天天开心！！！