贪心算法总结

1. 单调递增的数字

先来看第一种思路：

这种会超时，我们想想一下贪心的策略

直接上代码：

class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        string str = to_string(n); // 把数组转化为字符串
        int pos = 0;
        while(pos + 1 < str.size() && str[pos] <= str[pos + 1])
        {
            pos++;
        }
        // 走到这里两种情况
        // 1.一直走到尾都是递增的
        if(pos + 1 == str.size()) return n;
        // 2.走到中途停下来
        while(pos - 1 >= 0 && str[pos - 1] == str[pos])
        {
            pos--;
        }
        str[pos]--;
        for(int i = pos + 1; i < str.size(); i++)
        {
            str[i] = '9';
        }
        return stoi(str);
    }
};

2. 坏了的计算器

直接上思路：

直接上代码：

class Solution {
public:
    int brokenCalc(int startValue, int target) {
        int ret = 0;
        while(startValue < target)
        {
            if(target & 1 == 1) //奇数
            {
                target += 1;
            }
            else
            {
                target /= 2;
            }
            ret++; 
        }  
        return ret - target + startValue;;
    }
};

3. 合并区间

直接上思路：

上代码：

class Solution {
public:
    vectorint>> merge(vectorint>>& intervals) {
        // 先对照左端点排序
        sort(intervals.begin(), intervals.end());
        // 合并区间
        int left = intervals[0][0];
        int right = intervals[0][1];
        vectorint>> ret;
        for(int i = 1; i < intervals.size(); i++)
        {
            int a = intervals[i][0];
            int b = intervals[i][1];
            if(a <= right) // 有重叠部分
            {
                right = max(right, b); // 求并集
            }
            else
            {
                ret.push_back({left, right});
                left = a;
                right = b;
            }  
        }
        ret.push_back({left,right});
        return ret;
    }
};

4. 无重叠区间

直接上思路：

直接来写代码：

class Solution {
public:
    int eraseOverlapIntervals(vectorint>>& intervals) {
        sort(intervals.begin(),intervals.end()); // 左端点排序
        int right = intervals[0][1];
        int ret = 0;
        // 移除区间
        for(int i = 1; i < intervals.size(); i++)
        {
            int a = intervals[i][0];
            int b = intervals[i][1];
            if(right > a) // 重叠
            {
                right = min(right, b); // 贪心:删除右端点最大的区间
                ret++;
            }
            else
            {
                right = b;
            }
        }
        return ret;
    }
};

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

我们会发现这个题目依然是一个区间问题，所以做法依然是先对左端点排序，然后再想出一个贪心策略即可，我们只需要最少的弓箭数，那么一支箭应该引爆更多的气球，将两两互相重叠的所有区间都拿出来引爆。

直接上代码：

class Solution {
public:
    int findMinArrowShots(vectorint>>& points) {
        // 按照左端点进行排序
        sort(points.begin(), points.end());
        int right = points[0][1];
        int ret = 1;
        // 求互相重叠区间的数量
        for(int i = 1; i < points.size(); i++)
        {
            int a = points[i][0];
            int b = points[i][1];
            if(a <= right) // 有重叠部分
            {
                right = min(right, b);
            }
            else
            {
                right = b;
                ret++; // 此时无重复区间,需要再来一支箭 
            }
        }
        return ret;
    }
};