【贪心算法】day9

📝前言说明：

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

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

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

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

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;
                else
                    n += 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)$

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