【贪心算法】day9
📝前言说明：
- 本专栏主要记录本人的贪心算法学习以及LeetCode刷题记录，按专题划分
- 每题主要记录：（1）本人解法 + 本人屎山代码；（2）优质解法 + 优质代码；（3）精益求精，更好的解法和独特的思想（如果有的话）；（4）贪心策略正确性的 “证明”
- 文章中的理解仅为个人理解。如有错误，感谢纠错
🎬个人简介：努力学习ing
📋本专栏：C++刷题专栏
📋其他专栏：C语言入门基础，python入门基础，C++学习笔记，Linux
🎀ZEEKLOG主页 愚润泽
你可以点击下方链接，进行其他贪心算法题目的学习
| 点击链接 | 开始学习 |
|---|---|
| 贪心day1 | 贪心day2 |
| 贪心day3 | 贪心day4 |
| 贪心day5 | 贪心day6 |
| 贪心day7 | 贪心day8 |
| 贪心day9 | 贪心day10 |
也可以点击下面连接，学习其他算法
| 点击链接 | 开始学习 |
|---|---|
| 优选专题 | 动态规划 |
| 递归、搜索与回溯 | 贪心算法 |
题单获取→ 【贪心算法】题单汇总
题目
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)
🌈我的分享也就到此结束啦🌈
要是我的分享也能对你的学习起到帮助，那简直是太酷啦！
若有不足，还请大家多多指正，我们一起学习交流！
📢公主，王子：点赞👍→收藏⭐→关注🔍
感谢大家的观看和支持！祝大家都能得偿所愿，天天开心！！！
