【贪心算法】day8

📝前言说明：

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

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

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

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

991. 坏了的计算器

题目链接：https://leetcode.cn/problems/broken-calculator/description/

优质解

思路：

• 反向思考问题，利用double后数字必为偶数的特点
• 从 target 到 startValue(逆推) : 除法 or 加法(利用尽可能少的步骤)
  • 当 target < startValue: 只能加法
  • 当 target(且为偶数时) > startValue: 除法(因为加法会让数变大)
  • 当 target(且为奇数时) > stattValue: 加法(因为原来的数经过double不可能变成奇数)

代码：

class Solution {
public:
    int brokenCalc(int startValue, int target) {
        int ans = 0;
        while(target > startValue)
        {
            if(target % 2 == 0)
                target /= 2;
            else target += 1;
            ans++;
        }
        return ans + startValue - target;
    }
};

时间复杂度：$O(logtarget)$
空间复杂度：$O(1)$

56. 合并区间

题目链接：https://leetcode.cn/problems/merge-intervals/description/

优质解

思路：

• 区间问题：先排序，根据排序后结果的规律，得到解决问题的策略
  • 排序：按左端点 or 按右端点
• 本题解法
  • 按左端点排序，sort默认按左端点从小到大排序
  • 排序后，特征：同一组能够合并的区间都是连续的
    • 反证法：假如：中间出现一个不能合并的区间且后面还要有一个能合并的区间。
    • 对于不能合并的区间：左端点一定比“基准区间”的右端点大，
    • 又因为是排好序的，所以后面“能合并”区间的左端点也会比“基准区间”的右端点大（即不能合并，相互矛盾，所以特征成立）
• （重叠）求并区间
  • 左端点：必为"小"(前面)区间的左端点（因为是排好序的）
  • 右端点：为两个区间右端点的最大值

代码：

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& inter) {
        ranges::sort(inter);
        int n = inter.size();
        int left = inter[0][0], right = inter[0][1]; // "基准区间"
        vector<vector<int>> ans;
        for(int i = 1; i < n; i++)
        {
            int a = inter[i][0], b = inter[i][1];
            if(a <= right) // 代表有重叠区间
                right = max(b, right); // 合并区间
            else
            {
                ans.push_back({left, right}); // 把前面合并的区间添加进去
                left = a;
                right = b; // 更新基准区间
            }
        }
        ans.push_back({left, right}); // 添加最后一个区间
        return ans;
    }
};

时间复杂度：$O(nlogn)$，排序开销
空间复杂度：$O(n)$

435. 无重叠区间

题目链接：https://leetcode.cn/problems/non-overlapping-intervals/description/

优质解

思路：

• 多个连续的重叠区间，怎么确定移除哪一个"收益"最高呢？
  • 把范围较大的区间移除
  • 如果用左端点排序，则保留右端点小的区间
• 贪心策略（用右端点）：
  • 按照结束位置（右端点）排序
  • 如果有重叠区间，我们保留结束位置早的，以避免后面重叠的可能

代码：

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& inter) {
        ranges::sort(inter.begin(), inter.end(), [](vector<int>& a, vector<int>& b)
        {
            return a[1] < b[1]; // 按结束位置排序
        });
        int ans = 0, n = inter.size();
        int right = inter[0][1];
        for(int i = 1; i < n; i++)
        {
            int a = inter[i][0];
            if(right > a) ans++; // 把后一个重叠的区间移除，保留前面结束早的区间
            else right = inter[i][1]; // 更新"基准"
        }
        return ans;
    }
};

时间复杂度：$O(nlogn)$
空间复杂度：$O(n)$

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