算法沉淀——贪心算法六（leetcode真题剖析）

01.坏了的计算器

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

在显示着数字 startValue 的坏计算器上，我们可以执行以下两种操作：

• **双倍（Double）：**将显示屏上的数字乘 2；
• **递减（Decrement）：**将显示屏上的数字减 1 。

给定两个整数 startValue 和 target 。返回显示数字 target 所需的最小操作数。

示例 1：

输入：startValue = 2, target = 3
输出：2
解释：先进行双倍运算，然后再进行递减运算 {2 -> 4 -> 3}.
1
2
3

示例 2：

输入：startValue = 5, target = 8
输出：2
解释：先递减，再双倍 {5 -> 4 -> 8}.
1
2
3

示例 3：

输入：startValue = 3, target = 10
输出：3
解释：先双倍，然后递减，再双倍 {3 -> 6 -> 5 -> 10}.
1
2
3

思路

这里我们采用逆向思维的方式，更容易找到最短的计算次数，即使用目标值进行除法和加法运算逆推。

代码

class Solution {
public:
    int brokenCalc(int startValue, int target) {
        int ret=0;
        while(target>startValue){
            if(target%2) target++;
            else target/=2;
            ret++;
        }
        return ret+startValue-target;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

02.合并区间

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

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
1
2
3

示例 2：

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。 
1
2
3

提示：

• 1 <= intervals.length <= 104
• intervals[i].length == 2
• 0 <= starti <= endi <= 104

思路

这里我们要使用贪心思想，首先需要对整体进行排序，通过不断比较更新数组右区间的值，得到最大长度的区间数组。

代码

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(),intervals.end());

        int left=intervals[0][0],right=intervals[0][1];
        vector<vector<int>> ret;
        for(int i=1;i<intervals.size();i++){
            int a=intervals[i][0],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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

03.无重叠区间

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

给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。

示例 1:

输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。
1
2
3

示例 2:

输入: intervals = [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
1
2
3

示例 3:

输入: intervals = [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间，因为它们已经是无重叠的了。 
1
2
3

提示:

• 1 <= intervals.length <= 105
• intervals[i].length == 2
• -5 * 104 <= starti < endi <= 5 * 104

思路

首先我们按左端点排序，当两个区间重叠的时候，为了能保留更多的区间，我们应移除右端点较大的区间，代码的实现类似上一题

代码

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(),intervals.end());
        int ret=0;
        int left=intervals[0][0],right=intervals[0][1];
        for(int i=1;i<intervals.size();i++){
            int a=intervals[i][0],b=intervals[i][1];
            if(a<right){
                ret++;
                right=min(right,b);
            }
            else right=b;
        }
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

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

题目链接：https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/

有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。

一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 x``start，x``end， 且满足 xstart ≤ x ≤ x``end，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。

给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。

示例 1：

输入：points = [[10,16],[2,8],[1,6],[7,12]]
输出：2
解释：气球可以用2支箭来爆破:
-在x = 6处射出箭，击破气球[2,8]和[1,6]。
-在x = 11处发射箭，击破气球[10,16]和[7,12]。
1
2
3
4
5

示例 2：

输入：points = [[1,2],[3,4],[5,6],[7,8]]
输出：4
解释：每个气球需要射出一支箭，总共需要4支箭。
1
2
3

示例 3：

输入：points = [[1,2],[2,3],[3,4],[4,5]]
输出：2
解释：气球可以用2支箭来爆破:
- 在x = 2处发射箭，击破气球[1,2]和[2,3]。
- 在x = 4处射出箭，击破气球[3,4]和[4,5]。
1
2
3
4
5

提示:

• 1 <= points.length <= 105
• points[i].length == 2
• -231 <= xstart < xend <= 231 - 1

思路

按照左端点排序，这样互相重叠的区间都是连续的，这样，我们在射箭的时候，要发挥每一支箭最大的作用，应该把互相重叠的区间统一引爆。因为我们是按左端点排序的，因此对于两个区间，我们求的是他们的交集，左端点为两个区间左端点的最大值，右端点为两个区间的右端点的最小值。

代码

class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        sort(points.begin(),points.end());
        int right=points[0][1];
        int count=1;
        for(int i=1;i<points.size();i++){
            int a=points[i][0],b=points[i][1];
            if(a<=right) right=min(right,b);
            else count++,right=b;
        }
        return count;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14