01.壞了的計算器

題目鏈接：https://leetcode.cn/problems/broken-calculator/

在顯示著數(shù)字 startValue 的壞計算器上，我們可以執(zhí)行以下兩種操作：

• **雙倍（Double）：**將顯示屏上的數(shù)字乘 2；
• **遞減（Decrement）：**將顯示屏上的數(shù)字減 1 。

給定兩個整數(shù) startValue 和 target 。返回顯示數(shù)字 target 所需的最小操作數(shù)。

示例 1：

輸入：startValue = 2, target = 3
輸出：2
解釋：先進行雙倍運算，然后再進行遞減運算 {2 -> 4 -> 3}.

示例 2：

輸入：startValue = 5, target = 8
輸出：2
解釋：先遞減，再雙倍 {5 -> 4 -> 8}.

示例 3：

輸入：startValue = 3, target = 10
輸出：3
解釋：先雙倍，然后遞減，再雙倍 {3 -> 6 -> 5 -> 10}.

思路

這里我們采用逆向思維的方式，更容易找到最短的計算次數(shù)，即使用目標值進行除法和加法運算逆推。

代碼文章來源地址http://www.zghlxwxcb.cn/news/detail-847954.html

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;
    }
};

02.合并區(qū)間

題目鏈接：https://leetcode.cn/problems/merge-intervals/

以數(shù)組 intervals 表示若干個區(qū)間的集合，其中單個區(qū)間為 intervals[i] = [starti, endi] 。請你合并所有重疊的區(qū)間，并返回 一個不重疊的區(qū)間數(shù)組，該數(shù)組需恰好覆蓋輸入中的所有區(qū)間 。

示例 1：

輸入：intervals = [[1,3],[2,6],[8,10],[15,18]]
輸出：[[1,6],[8,10],[15,18]]
解釋：區(qū)間 [1,3] 和 [2,6] 重疊, 將它們合并為 [1,6].

示例 2：

輸入：intervals = [[1,4],[4,5]]
輸出：[[1,5]]
解釋：區(qū)間 [1,4] 和 [4,5] 可被視為重疊區(qū)間。 

提示：

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

思路

這里我們要使用貪心思想，首先需要對整體進行排序，通過不斷比較更新數(shù)組右區(qū)間的值，得到最大長度的區(qū)間數(shù)組。

代碼

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;
    }
};

03.無重疊區(qū)間

題目鏈接：https://leetcode.cn/problems/non-overlapping-intervals/

給定一個區(qū)間的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除區(qū)間的最小數(shù)量，使剩余區(qū)間互不重疊 。

示例 1:

輸入: intervals = [[1,2],[2,3],[3,4],[1,3]]
輸出: 1
解釋: 移除 [1,3] 后，剩下的區(qū)間沒有重疊。

示例 2:

輸入: intervals = [ [1,2], [1,2], [1,2] ]
輸出: 2
解釋: 你需要移除兩個 [1,2] 來使剩下的區(qū)間沒有重疊。

示例 3:

輸入: intervals = [ [1,2], [2,3] ]
輸出: 0
解釋: 你不需要移除任何區(qū)間，因為它們已經(jīng)是無重疊的了。 

提示:

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

思路

首先我們按左端點排序，當兩個區(qū)間重疊的時候，為了能保留更多的區(qū)間，我們應移除右端點較大的區(qū)間，代碼的實現(xiàn)類似上一題

代碼

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;
    }
};

04.用最少數(shù)量的箭引爆氣球

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

有一些球形氣球貼在一堵用 XY 平面表示的墻面上。墻面上的氣球記錄在整數(shù)數(shù)組 points ，其中points[i] = [xstart, xend] 表示水平直徑在 xstart 和 xend之間的氣球。你不知道氣球的確切 y 坐標。

一支弓箭可以沿著 x 軸從不同點 完全垂直 地射出。在坐標 x 處射出一支箭，若有一個氣球的直徑的開始和結(jié)束坐標為 x``start，x``end， 且滿足 xstart ≤ x ≤ x``end，則該氣球會被 引爆 ?？梢陨涑龅墓臄?shù)量 沒有限制 。 弓箭一旦被射出之后，可以無限地前進。

給你一個數(shù)組 points ，返回引爆所有氣球所必須射出的 最小 弓箭數(shù) 。

示例 1：

輸入：points = [[10,16],[2,8],[1,6],[7,12]]
輸出：2
解釋：氣球可以用2支箭來爆破:
-在x = 6處射出箭，擊破氣球[2,8]和[1,6]。
-在x = 11處發(fā)射箭，擊破氣球[10,16]和[7,12]。

示例 2：

輸入：points = [[1,2],[3,4],[5,6],[7,8]]
輸出：4
解釋：每個氣球需要射出一支箭，總共需要4支箭。

示例 3：

輸入：points = [[1,2],[2,3],[3,4],[4,5]]
輸出：2
解釋：氣球可以用2支箭來爆破:
- 在x = 2處發(fā)射箭，擊破氣球[1,2]和[2,3]。
- 在x = 4處射出箭，擊破氣球[3,4]和[4,5]。

提示:

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

思路

按照左端點排序，這樣互相重疊的區(qū)間都是連續(xù)的，這樣，我們在射箭的時候，要發(fā)揮每一支箭最大的作用，應該把互相重疊的區(qū)間統(tǒng)一引爆。因為我們是按左端點排序的，因此對于兩個區(qū)間，我們求的是他們的交集，左端點為兩個區(qū)間左端點的最大值，右端點為兩個區(qū)間的右端點的最小值。

代碼

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;
    }
};

到了這里，關(guān)于算法沉淀——貪心算法六（leetcode真題剖析）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！