算法训练 | 贪心算法Part5 | 435.无重叠区间、763.划分字母区间、56. 合并区间、738.单调递增的数字

目录

435.无重叠区间

贪心算法

763.划分字母区间

贪心算法

56. 合并区间

贪心算法

738.单调递增的数字

贪心算法

435.无重叠区间

• 题目链接：435. 无重叠区间 - 力扣（LeetCode）

• 文章讲解：代码随想录

  贪心算法

  • 解题思路

    • 按照右边界排序，还是按照左边界排序呢？其实都可以。主要就是为了让区间尽可能的重叠。

    • 按照右边界排序，从左向右记录非交叉区间的个数。最后用区间总数减去非交叉区间的个数就是需要移除的区间个数了。此时问题就是要求非交叉区间的最大个数。

  • 解题步骤

    • 区间，1，2，3，4，5，6都按照右边界排好序。

    • 当确定区间 1 和 区间2 重叠后，取 区间1 和 区间2 右边界的最小值，因为这个最小值之前的部分一定是 区间1 和区间2 的重合部分，如果这个最小值也触达到区间3，那么说明 区间 1，2，3都是重合的。

    • 接下来就是找大于区间1结束位置的区间，是从区间4开始。那有同学问了为什么不从区间5开始？别忘了已经是按照右边界排序的了。

    • 区间4结束之后，再找到区间6，所以一共记录非交叉区间的个数是三个。

    • 总共区间个数为6，减去非交叉区间的个数3。移除区间的最小数量就是3。

  • 代码一：左区间优化 ⭐

    class Solution {
    public:
        static bool cmp (const vector& a, const vector& b) {
            return a[0]  
    763.划分字母区间 
     
    

    • 题目链接：763. 划分字母区间 - 力扣（LeetCode）

    • 文章讲解：代码随想录

      贪心算法

      • 解题思路

        • 题目要求同一字母最多出现在一个片段中，那么如何把同一个字母的都圈在同一个区间里。

        • 在遍历的过程中相当于是要找每一个字母的边界，如果找到之前遍历过的所有字母的最远边界，说明这个边界就是分割点了。此时前面出现过所有字母，最远也就到这个边界了。

      • 解题步骤

        • 统计每一个字符最后出现的位置

        • 从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点

      • 代码一：贪心算法

        class Solution {
        public:
            vector partitionLabels(string S) {
                int hash[27] = {0}; // i为字符，hash[i]为字符出现的最后位置
                for (int i = 0; i  
        56. 合并区间 
         
        

        • 题目链接：56. 合并区间 - 力扣（LeetCode）

        • 文章讲解：代码随想录

          贪心算法

          • 解题思路

            • 先排序，让所有的相邻区间尽可能的重叠在一起，按左边界，或者右边界排序都可以，处理逻辑稍有不同。

            • 按照左边界从小到大排序之后，如果 intervals[i][0] strNum[i]的情况，让strNum[i - 1]减一，但此时如果strNum[i - 1]减一了，可能又小于strNum[i - 2]。举个例子，数字：332，从前向后遍历的话，那么就把变成了329，此时2又小于了第一位的3了，真正的结果应该是299。

            • 那么从后向前遍历，就可以重复利用上次比较得出的结果了，从后向前遍历332的数值变化为：332 -> 329 -> 299确定了遍历顺序之后，那么此时局部最优就可以推出全局

          • 代码一：贪心算法

            // 时间复杂度：O(n)，n 为数字长度
            // 空间复杂度：O(n)，需要一个字符串，转化为字符串操作更方便
            class Solution {
            public:
                int monotoneIncreasingDigits(int N) {
                    string strNum = to_string(N);
                    // flag用来标记赋值9从哪里开始
                    // 设置为这个默认值，为了防止第二个for循环在flag没有被赋值的情况下执行
                    int flag = strNum.size();
                    for (int i = strNum.size() - 1; i > 0; i--) {
                        if (strNum[i - 1] > strNum[i] ) {
                            flag = i;
                            strNum[i - 1]--;
                        }
                    }
                    for (int i = flag; i