一舉拿下貪心

大家好，我是Simon郎，一個每天想要博學一點點的小青年！

今天為大家分享的是貪心算法。

貪心算法：貪心算法（又稱貪婪算法）是指，在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，算法得到的是在某種意義上的局部最優(yōu)解，從而使得得到的最終結果是全局最優(yōu)或者接近于全局最優(yōu)。

本文選取LeetCode比較有代表性的題目來學習貪心算法，選取的題目如下:

• 1、分發(fā)餅干(455)

• 2、分發(fā)糖果(135)

• 3、無重疊區(qū)間(435)

• 4、種花問題(605)

• 5、用最少數(shù)量的箭引爆氣球(452)

• 6、劃分字母區(qū)間(763)

• 7、買賣股票的最佳時機(122)

• 8、根據(jù)身高重建隊列(406)

• 9、非遞減數(shù)列(665)

每道題目都有五部分組成：

• 題目描述
• 示例
• 解題思路
• 代碼實現(xiàn)
• 執(zhí)行結果

1、分發(fā)餅干(455)

題目描述：

假設你是一位很棒的家長，想要給你的孩子們一些小餅干。但是，每個孩子最多只能給一塊餅干。

對每個孩子 i，都有一個胃口值 g[i]，這是能讓孩子們滿足胃口的餅干的最小尺寸；并且每塊餅干 j，都有一個尺寸 s[j] 。如果 s[j] >= g[i]，我們可以將這個餅干 j 分配給孩子 i ，這個孩子會得到滿足。你的目標是盡可能滿足越多數(shù)量的孩子，并輸出這個最大數(shù)值。

示例:

示例1：

輸入: g = [1,2,3], s = [1,1] 

輸出: 1 

解釋: 你有三個孩子和兩塊小餅干，3個孩子的胃口值分別是：1,2,3。雖然你有兩塊小餅干，由于他們的尺寸都是1，你只能讓胃口值是1的孩子滿足。所以你應該輸出1

示例2：

輸入: g = [1,2], s = [1,2,3] 

輸出: 2 

解釋: 你有兩個孩子和三塊小餅干，2個孩子的胃口值分別是1,2。你擁有的餅干數(shù)量和尺寸都足以讓所有孩子滿足。所以你應該輸出2.

思路:

采用貪心算法：大尺寸的餅干能夠滿足胃口小的孩子，也能夠滿足胃口大的孩子，所以對于大尺寸的餅干要優(yōu)先滿足胃口大的孩子，而胃口小的孩子用小尺寸的餅干來喂，盡量減少浪費。

局部最優(yōu)：充分利用餅干尺寸滿足一個；全局最優(yōu)：就是滿足盡可能多的孩子

首先將餅干數(shù)組和孩子數(shù)組進行排序，然后從前往后依次進行比較。

胃口比餅干尺寸小，孩子被滿足，繼續(xù)遍歷下一個孩子和下一塊餅干； 胃口比餅干尺寸大，遍歷下一塊餅干。

代碼：

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int child=0, cookie=0;
        while(child<g.length && cookie<s.length){
            if(g[child]<=s[cookie]) child++;
            cookie++;
        }
     return child;
    }
}

執(zhí)行結果：

2、分發(fā)糖果(135)

題目描述：

老師想給孩子們分發(fā)糖果，有 N 個孩子站成了一條直線，老師會根據(jù)每個孩子的表現(xiàn)，預先給他們評分。你需要按照以下要求，幫助老師給這些孩子分發(fā)糖果：每個孩子至少分配到 1 個糖果。評分更高的孩子必須比他兩側的鄰位孩子獲得更多的糖果。

那么這樣下來，老師至少需要準備多少顆糖果呢？

示例：

示例 1：

輸入：[1,0,2] 

輸出：5 

解釋：你可以分別給這三個孩子分發(fā) 2、1、2 顆糖果。

示例 2：

輸入：[1,2,2] 

輸出：4 

解釋：你可以分別給這三個孩子分發(fā) 1、2、1 顆糖果。第三個孩子只得到 1 顆糖果，這已滿足上述兩個條件。

解題思路：

相鄰孩子，評分高的孩子必須獲得更多的糖果，因此拆分成兩個規(guī)則：

• 規(guī)則定義：設學生A和學生B左右相鄰，A在B的左邊

左規(guī)則：當B>A時，B的糖果比A的數(shù)量多

右規(guī)則：當A>B時，則A的糖果比B的糖果數(shù)量多

相鄰的學生中，評分高的學生必須獲得更多的糖果 等價于 所有學生滿足左規(guī)則且滿足右規(guī)則。

• 算法流程

• 把所有孩子的糖果數(shù)初始化為 1。
• 先從左往右遍歷一遍，如果右邊孩子的評分比左邊的高，則右邊孩子的糖果數(shù)更新為左邊孩子的 糖果數(shù)加 1。
• 再從右往左遍歷一遍，如果左邊孩子的評分比右邊的高，且左邊孩子當前的糖果數(shù) 不大于右邊孩子的糖果數(shù)，則左邊孩子的糖果數(shù)更新為右邊孩子的糖果數(shù)加 1。

代碼：

class Solution {
    public int candy(int[] ratings) {
        //循環(huán)遍歷兩次
        int[] candy=new int[ratings.length];
        int count=candy.length;
        for(int i=1;i<ratings.length;i++){
            if(ratings[i-1]<ratings[i]){
                candy[i]=candy[i-1]+1;
            }
        }  
        for(int j=ratings.length-1;j>0;j--){
            if(ratings[j]<ratings[j-1]){
                candy[j-1]=Math.max(candy[j-1],candy[j]+1);
            }
        }
        for(int k=0;k<candy.length;k++){
            count+=candy[k];
        }
        return count;
    }
}

執(zhí)行結果：

3、無重疊區(qū)間(435)

題目描述：

給定一個區(qū)間的集合，找到需要移除區(qū)間的最小數(shù)量，使剩余區(qū)間互不重疊。

注意：可以認為區(qū)間的終點總是大于它的起點；區(qū)間[1,2]和[2,3]的邊界相互接觸，但沒有相互重疊

示例：

示例 1:

輸入: [ [1,2], [2,3], [3,4], [1,3] ]

輸出: 1

解釋: 移除 [1,3] 后，剩下的區(qū)間沒有重疊。

示例 2:

輸入: [ [1,2], [1,2], [1,2] ]

輸出: 2

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

示例 3:

輸入: [ [1,2], [2,3] ]

輸出: 0

解釋: 你不需要移除任何區(qū)間，因為它們已經(jīng)是無重疊的了。

解題思路：

首先要對區(qū)間進行排序，本題采用的是對區(qū)間的頭元素進行排序，然后在遍歷空間

• 如果后面區(qū)間的頭小于當前區(qū)間的尾，比如當前區(qū)間是[3,6]，后面區(qū)間是[4,5]或者是[5,9],說明這兩個區(qū)間有重復，必須要移除一個，那么要移除哪個呢，為了防止在下一個區(qū)間和現(xiàn)有區(qū)間有重疊，我們應該讓現(xiàn)有區(qū)間越短越好，所以應該移除尾部比較大的，保留尾部比較小的。
• 如果后面區(qū)間的頭不小于當前區(qū)間的尾，說明他們沒有重合，不需要移除

代碼：

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        //對2*2數(shù)組按照左邊界排序
        Arrays.sort(intervals,(a,b)->a[0]-b[0]);
        int end=intervals[0][1];
        int count=0;
        for(int i=1;i<intervals.length;i++){
            if(intervals[i][0]<end){
                //區(qū)間有重疊,選取右邊界最小的數(shù)組
                end=Math.min(end,intervals[i][1]);
                count++;
            }else{
                //區(qū)間無重疊，直接更新就好
                end=intervals[i][1];
            }
          
        }
        return count;
    }
}

執(zhí)行結果：

4、種花問題(605)

題目描述：

假設有一個很長的花壇，一部分地塊種植了花，另一部分卻沒有。可是，花不能種植在相鄰的地塊上，它們會爭奪水源，兩者都會死去。

給你一個整數(shù)數(shù)組  flowerbed 表示花壇，由若干 0 和 1 組成，其中 0 表示沒種植花，1 表示種植了花。另有一個數(shù) n ，能否在不打破種植規(guī)則的情況下種入 n 朵花？能則返回 true ，不能則返回 false

示例：

示例 1：

輸入：flowerbed = [1,0,0,0,1], n = 1 輸出：true

示例 2：

輸入：flowerbed = [1,0,0,0,1], n = 2 輸出：false

解題思路：

題目要求是否能在不打破規(guī)則的情況下插入n朵花，與直接計算不同，采用“跳格子”的解法只需遍歷不到一遍數(shù)組，處理以下兩種不同的情況即可：

• 當遍歷到index遇到1時，說明這個位置有花，那必然從index+2的位置才有可能種花，因此當碰到1時直接跳過下一格。
• 當遍歷到index遇到0時，由于每次碰到1都是跳兩格，因此前一格必定是0，此時只需要判斷下一格是不是1即可得出index這一格能不能種花，如果能種則令n減一，然后這個位置就按照遇到1時處理，即跳兩格；如果index的后一格是1，說明這個位置不能種花且之后兩格也不可能種花,直接跳過3格。

當n減為0時，說明可以種入n朵花，則可以直接退出遍歷返回true；如果遍歷結束n沒有減到0，說明最多種入的花的數(shù)量小于n，則返回false。

代碼：

class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
         //采用跳格子的思想解決
         //1，index為1，跳兩格
         //2 index為0，證明前一個格子是0，只需要判斷下一個格子是否為0
         //若為0，則n-1,
         //若為1，則跳三格
         for(int i=0;i<flowerbed.length && n>0;){
             if(flowerbed[i]==1){
                 i=i+2;
                 //一定要注意邊界問題
             } else if(i==flowerbed.length-1 || flowerbed[i+1]==0){
                    n--;
                    i=i+2;
             }else{
                    i=i+3;
                }
         }
         return n<=0;
    }
}

執(zhí)行結果：

5、用最少數(shù)量的箭引爆氣球(452)

題目描述：

在二維空間中有許多球形的氣球。對于每個氣球，提供的輸入是水平方向上，氣球直徑的開始和結束坐標。由于它是水平的，所以縱坐標并不重要，因此只要知道開始和結束的橫坐標就足夠了。開始坐標總是小于結束坐標。

一支弓箭可以沿著 x 軸從不同點完全垂直地射出。在坐標 x 處射出一支箭，若有一個氣球的直徑的開始和結束坐標為 xstart，xend， 且滿足  xstart ≤ x ≤ xend，則該氣球會被引爆。可以射出的弓箭的數(shù)量沒有限制。弓箭一旦被射出之后，可以無限地前進。我們想找到使得所有氣球全部被引爆，所需的弓箭的最小數(shù)量。

給你一個數(shù)組 points ，其中 points [i] = [xstart,xend] ，返回引爆所有氣球所必須射出的最小弓箭數(shù)。

示例：

示例 1：

輸入：points = [[10,16],[2,8],[1,6],[7,12]] 輸出：2 解釋：對于該樣例，x = 6 可以射爆 [2,8],[1,6] 兩個氣球，以及 x = 11 射爆另外兩個氣球

示例 2：

輸入：points = [[1,2],[3,4],[5,6],[7,8]] 輸出：4

示例 3：

輸入：points = [[1,2],[2,3],[3,4],[4,5]] 輸出：2

示例 4：

輸入：points = [[1,2]] 輸出：1

示例 5：

輸入：points = [[2,3],[2,3]] 輸出：1

解題思路：

首先想到的思路是對數(shù)組中的區(qū)間值按左端點進行排序

• 如果新氣球的左端點大于射擊區(qū)間的右邊界，那么我們就需要重新開辟一個區(qū)間；

• 如果新氣球的左端點小于射擊區(qū)間的右邊界，這里又要分為兩種情況：如果右端點大于射擊區(qū)間的右邊界，那么我們的射擊區(qū)間的右邊界無需變化；如果右端點小于射擊區(qū)間的右邊界，那么我們射擊區(qū)間的右邊界就要向左移動，以新氣球的右端點為準，確立新的邊界。

代碼：

class Solution {
    public int findMinArrowShots(int[][] points) {
    //貪心算法，找出一支箭引爆最多的氣球的
        if(points.length==0) return 0;
    //對二維數(shù)組按照左邊界從小到大排休排序
    Arrays.sort(points,(a,b)->a[0]<b[0]?-1:1);
    int right=points[0][1];
    int count=1;
    for(int i=1;i<points.length;i++){
        if(points[i][0]>right){
            count++;
            right=points[i][1];
        }
        else{
            if(points[i][1]<right){
                right=points[i][1];
            }
        }
    } 
    return count;
    }
}

執(zhí)行結果：

6、劃分字母區(qū)間(763)

題目描述：

字符串 S 由小寫字母組成。我們要把這個字符串劃分為盡可能多的片段，同一字母最多出現(xiàn)在一個片段中。返回一個表示每個字符串片段的長度的列表。

示例：

輸入：S = "ababcbacadefegdehijhklij" 

輸出：[9,7,8]

解釋：劃分結果為 "ababcbaca", "defegde", "hijhklij"。每個字母最多出現(xiàn)在一個片段中。像 "ababcbacadefegde", "hijhklij" 的劃分是錯誤的，因為劃分的片段數(shù)較少。

解題思路：

由于同一個字母只能出現(xiàn)在同一個片段，顯然同一個字母的第一次出現(xiàn)的下標位置和最后一次出現(xiàn)的下標位置必須出現(xiàn)在同一個片段。因此需要遍歷字符串，得到每個字母最后一次出現(xiàn)的下標位置。

在得到每個字母最后一次出現(xiàn)的下標位置之后，可以使用貪心的方法將字符串劃分為盡可能多的片段，具體做法如下。

• 從左到右遍歷字符串，遍歷的同時維護當前片段的開始下標start和結束下標end，初始化start=end=0。
• 對于每個訪問到的字母，得到當前字母的最后一次出現(xiàn)的下標位置end1，則當前片段的結束下標一定不會小于end1，因此，令end=max（end,end1）
• 當訪問到下標end 時，當前片段訪問結束，當前片段的下標范圍是 [start,end]，長度為end?start+1，將當前片段的長度添加到返回值，然后令 start=end+1，繼續(xù)尋找下一個片段
• 重復上述過程，直至遍歷完字符串

代碼：

class Solution {
    public List<Integer> partitionLabels(String s) {
        //先生成一個長度為26的數(shù)組，用于存放每個的不同字符在序列中的最終位置
        int[] alphabet=new int[26];
        List list=new ArrayList<>();
        int start=0, end=0;
        for(int i=0;i<s.length();i++){
            alphabet[s.charAt(i)-'a']=i;
        }

        for(int i=0;i<s.length();i++){
            end=Math.max(end,alphabet[s.charAt(i)-'a']);
            if(end==i){
                list.add(end-start+1);
                start=end+1;
            }
        }
        return list;
    }
}

執(zhí)行結果：

7、買賣股票的最佳時機(122)

題目描述：

給定一個數(shù)組 prices ，其中 prices[i] 是一支給定股票第 i 天的價格。設計一個算法來計算你所能獲取的最大利潤。你可以盡可能地完成更多的交易（多次買賣一支股票）。

注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。

示例：

示例 1:

輸入: prices = [7,1,5,3,6,4] 

輸出: 7 

解釋: 在第 2 天（股票價格 = 1）的時候買入，在第 3 天（股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 。隨后，在第 4 天（股票價格 = 3）的時候買入，在第 5 天（股票價格 = 6）的時候賣出, 這筆交易所能獲得利潤 = 6-3 = 3 。 

示例 2:

輸入: prices = [1,2,3,4,5] 

輸出: 4

解釋: 在第 1 天（股票價格 = 1）的時候買入，在第 5 天 （股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 。注意你不能在第 1 天和第 2 天接連購買股票，之后再將它們賣出。因為這樣屬于同時參與了多筆交易，你必須在再次購買前出售掉之前的股票。 

示例 3:

輸入: prices = [7,6,4,3,1]

輸出: 0 

解釋: 在這種情況下, 沒有交易完成, 所以最大利潤為 0。

解題思路：

• 由于該題可以買賣無限次，只要第二天的價格大于前一天的價格我們就買前一天的股票，然后在第二天賣掉，這樣我們就能從中獲取利潤；
• 反之，如果第二天的價格小于前一天的價格我們就不進行買賣。

代碼：

class Solution {
    public int maxProfit(int[] prices) {
        //
        int sum=0;
        int start=0, end=0;
        for(int i=1;i<prices.length;i++){
            if(prices[i]-prices[i-1]>0){
                sum+=prices[i]-prices[i-1];
            }
        }
        return sum;
    }
}

執(zhí)行結果

8、根據(jù)身高重建隊列(406)

題目描述：

假設有打亂順序的一群人站成一個隊列，數(shù)組 people 表示隊列中一些人的屬性（不一定按順序）。每個 people[i] = [hi, ki] 表示第 i 個人的身高為 hi ，前面 正好 有 ki 個身高大于或等于 hi 的人。

請你重新構造并返回輸入數(shù)組 people 所表示的隊列。返回的隊列應該格式化為數(shù)組 queue ，其中 queue[j] = [hj, kj] 是隊列中第 j 個人的屬性（queue[0] 是排在隊列前面的人）。

示例：

示例 1：

輸入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]] 

輸出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 

解釋：編號為 0 的人身高為 5 ，沒有身高更高或者相同的人排在他前面。編號為 1 的人身高為 7 ，沒有身高更高或者相同的人排在他前面。編號為 2 的人身高為 5 ，有 2 個身高更高或者相同的人排在他前面，即編號為 0 和 1 的人。編號為 3 的人身高為 6 ，有 1 個身高更高或者相同的人排在他前面，即編號為 1 的人。編號為 4 的人身高為 4 ，有 4 個身高更高或者相同的人排在他前面，即編號為 0、1、2、3 的人。編號為 5 的人身高為 7 ，有 1 個身高更高或者相同的人排在他前面，即編號為 1 的人。因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新構造后的隊列。

示例 2：

輸入：people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]] 

輸出：[[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]

解題思路：

一般這種數(shù)對，還涉及排序的，根據(jù)第一個元素正向排序，根據(jù)第二個元素反向排序，或者根據(jù)第一個元素反向排序，根據(jù)第二個元素正向排序，往往能夠簡化解題過程。

在本題目中，首先對數(shù)對進行排序，按照數(shù)對的元素 1 降序排序，按照數(shù)對的元素 2 升序排序。

原因是：按照元素 1 進行降序排序，對于每個元素，在其之前的元素的個數(shù)，就是大于等于他的元素的數(shù)量，而按照第二個元素正向排序，我們希望 k 大的盡量在后面，減少插入操作的次數(shù)。

代碼：

class Solution {
    public int[][] reconstructQueue(int[][] people) {
      // [7,0], [7,1], [6,1], [5,0], [5,2], [4,4]
        // 再一個一個插入。
        // [7,0]
        // [7,0], [7,1]
        // [7,0], [6,1], [7,1]
        // [5,0], [7,0], [6,1], [7,1]
        // [5,0], [7,0], [5,2], [6,1], [7,1]
        // [5,0], [7,0], [5,2], [6,1], [4,4], [7,1]
        Arrays.sort(people, (o1, o2) -> o1[0] == o2[0] ? o1[1] - o2[1] : o2[0] - o1[0]);

        LinkedList<int[]> list = new LinkedList<>();
        for (int[] i : people) {
            list.add(i[1], i);
        }

        return list.toArray(new int[list.size()][2]);
    }
}

執(zhí)行結果

9、非遞減數(shù)列(665)

題目描述：

給你一個長度為 n 的整數(shù)數(shù)組，請你判斷在 最多 改變 1 個元素的情況下，該數(shù)組能否變成一個非遞減數(shù)列。

我們是這樣定義一個非遞減數(shù)列的：對于數(shù)組中任意的 i (0 <= i <= n-2)，總滿足 nums[i] <= nums[i + 1]。

示例：

示例 1:

輸入: nums = [4,2,3] 輸出: true 解釋: 你可以通過把第一個4變成1來使得它成為一個非遞減數(shù)列。

示例 2:

輸入: nums = [4,2,1] 輸出: false 解釋: 你不能在只改變一個元素的情況下將其變?yōu)榉沁f減數(shù)列。

解題思路：

本題是要維持一個非遞減的數(shù)列，所以遇到遞減的情況時（nums[i] > nums[i + 1]），要么將前面的元素縮小，要么將后面的元素放大。

但是本題唯一的易錯點就在這，

如果將nums[i]縮小，可能會導致其無法融入前面已經(jīng)遍歷過的非遞減子數(shù)列；如果將nums[i + 1]放大，可能會導致其后續(xù)的繼續(xù)出現(xiàn)遞減；所以要采取貪心的策略，在遍歷時，每次需要看連續(xù)的三個元素，也就是瞻前顧后，遵循以下兩個原則：

需要盡可能不放大nums[i + 1]，這樣會讓后續(xù)非遞減更困難；如果縮小nums[i]，但不破壞前面的子序列的非遞減性；算法步驟：

遍歷數(shù)組，如果遇到遞減：還能修改：

修改方案1：將nums[i]縮小至nums[i + 1]

修改方案2：將nums[i + 1]放大至nums[i]；不能修改了：直接返回false

代碼：

class Solution {
    public boolean checkPossibility(int[] nums) {
        if(nums.length==1) return true;
        boolean flag=nums[0]<=nums[1]?true:false;
        for(int i=1;i<nums.length-1;i++){
            if(nums[i+1]<nums[i]){
                if(flag){
                    if(nums[i+1]>=nums[i-1])
                        nums[i]=nums[i+1];
                    else
                        nums[i+1]=nums[i];
                    flag=false;
                }
                else 
                   return false;
            }
        }
        return true;
    }
}

執(zhí)行結果