目錄
什么是貪心算法？
leetcode455題.分發餅干
leetcode376題.擺動序列
leetcode55題.跳躍游戲I
leetcode45題.跳躍游戲II
leetcode621題.任務調度器
leetcode435題.無重疊空間
leetcode135題.分發糖果
什么是貪心算法？
貪心算法更多的是一種思想，沒什么套路。
貪心：顧名思義，貪心就是只顧眼前的利益。只關注局部最優解，當前狀態的最優解，不關注最后全局最優解。
舉個正面例子：從不同面額的人民幣中選十張，怎么選金額最大？貪心算法就會每次都選100元面額的人民幣，選十張后得到的金額剛好也是全局最優解。
舉個反面例子：有一個承重10斤的包，有五個石頭，重量分別是7、4、5、4、2斤，怎樣放才能讓背包利用率最大？貪心算法就會每次都選最大的，先是7斤，然后再選2斤，總共利用了9斤。而全局最優的解法應該是：4 + 4 + 2 = 10斤。所以貪心算法不一定是最優解。
我們學貪心算法是希望能夠通過局部最優解推算出全局最優解。我們有什么套路呢？答案是沒有。對于一道題你無法用套路來推算能否用貪心算法做，我們只能靠直覺+自己多做題，通過刷題來掌握常見的貪心算法題。面試時貪心考的不多，我們重點掌握七八道核心題就可以了。
leetcode455題.分發餅干
455. 分發餅干 - 力扣（LeetCode）
思路：我們可以把小尺寸的餅干盡可能地給胃口小的孩子，或者大尺寸餅干盡量給胃口大的孩子。?
class Solution {public int findContentChildren(int[] g, int[] s) {Arrays.sort(g);//按照胃口大小給孩子們排序Arrays.sort(s);//按照餅干尺寸給餅干排序//長度int n = g.length;//孩子個數int m = s.length;//餅干個數int res = 0;//存放結果//遍歷餅干，把小尺寸餅干給小胃口的孩子for(int i = 0; res < n && i < m; i++){//如果餅干尺寸大于等于孩子的胃口if(s[i] >= g[res]){res++;//那就下一個孩子}}return res;//時間復雜度：nlogn+mlogm 空間復雜度O（1）}
}leetcode376題.擺動序列
376. 擺動序列 - 力扣（LeetCode）
class Solution {public int wiggleMaxLength(int[] nums) {if(nums.length == 1) return nums.length;int res = 1;//防止最后一個峰值丟失int pre = 0;//保存前一個峰值是正是負int cur = 0;//保存當前差值for(int i = 0; i < nums.length - 1; i++){cur = nums[i + 1] - nums[i];if(pre <= 0 && cur > 0 || pre >= 0 && cur < 0){res++;pre = cur;}}return res;}
}leetcode55題.跳躍游戲I
55. 跳躍游戲 - 力扣（LeetCode）
?1）如果從當前位置可以跳到位置i，表示i之前的所有位置我們都能到達。
2）我們要盡可能地跳的遠一點。
3）判斷自己能否到達最后一個位置。
class Solution {public boolean canJump(int[] nums) {int max = 0;//我們能跳到的最遠的位置for(int i = 0; i < nums.length; i++){if(max < i){return false;//連i這個位置都到不了}max = Math.max(max, i + nums[i]);}return true;}
}leetcode45題.跳躍游戲II
45. 跳躍游戲 II - 力扣（LeetCode）
?
class Solution {public int jump(int[] nums) {int start = 0;int end = 0;int res = 0;int max = 0;//能夠跳躍的最遠的位置while(end < nums.length){if(max >= nums.length - 1) return res;for(int i = start; i <= end; i++){max = Math.max(max, i + nums[i]); }res++;start = end + 1;//表示下一次跳躍的起始位置end = max;//end是當前能跳躍的最遠的位置}return res;}
}leetcode621題.任務調度器
621. 任務調度器 - 力扣（LeetCode）
?
class Solution {public int leastInterval(char[] tasks, int n) {//找出出現次數最多的字母int []arr = new int[26];int k = 0;//假設出現次數最多的字母有k種for(int i = 0; i < tasks.length; i++){arr[tasks[i] - 'A']++;//第 i 個元素的 ASCII 碼減去字符 'A' 的 ASCII 碼，得到的結果作為索引值//計算出該字母與字母 'A' 之間的偏移量。然后，這個偏移量被用作索引值}int max = 0;for(int i = 0; i < 26; i++){max = Math.max(max, arr[i]);}for(int i = 0; i < 26; i++){if(arr[i] == max){k++;}}//間隔夠插和不夠插中的最大值max = Math.max(((max - 1)*(n + 1) + k), tasks.length);return max;}
}leetcode435題.無重疊空間
435. 無重疊區間 - 力扣（LeetCode）
?
class Solution {//轉化問題-——>保存最大的區間數量使得區間不重疊//我們要留下在不重疊的情況下，右邊界比較小的區間//步驟：對數組排序，以第二個元素排序// 之后遍歷數組，遇到不重疊的就選擇留下來public int eraseOverlapIntervals(int[][] intervals) {if(intervals.length <= 1) return 0;//Arrays.sort() 方法的第二個參數是一個比較器（Comparator）//對二維數組 intervals 按照每個子數組的第二個元素進行升序排序。/*當我們使用如 Arrays.sort() 這樣的方法進行排序時，元素的實際交換操作是在單獨的排序算法（如快速排序、歸并排序等）中進行的，而比較器僅負責提供元素之間的相對順序信息。這些排序算法會根據比較器的返回值來更新元素間的相對順序，并在適當的時候實際交換元素的位置，最終得到一個有序序列。 */Arrays.sort(intervals, new Comparator<int[]>(){//重寫comparepublic int compare(int[] s1, int[] s2){return s1[1] - s2[1];}});int max = 1;//表示當前已經選擇的不重疊區間的數量int right = intervals[0][1];for(int i = 1; i < intervals.length; i++){if(intervals[i][0] >= right){max++;right = intervals[i][1];}}return intervals.length - max;}
}leetcode135題.分發糖果
135. 分發糖果 - 力扣（LeetCode）
?
class Solution {public int candy(int[] ratings) {//孩子糖數受左右兩邊相鄰的孩子影響/*左規則：如果只受左邊孩子的影響，比左邊的孩子分數高就比左邊的孩子多獲得一個糖果右規則：如果只受右邊孩子影響，比右邊孩子的分數高就多獲得一個糖果整體結合左右規則來看，就在判斷每個孩子的糖果數中取兩個規則中的較大數 */int[] left = new int[ratings.length];int[] right = new int[ratings.length];//填充左規則left[0] = 1;for(int i = 1; i < ratings.length; i++){if(ratings[i] > ratings[i - 1]){left[i] = left[i - 1] + 1;}else{left[i] = 1;}}//填充右規則right[ratings.length - 1] = 1;for(int i = ratings.length - 2; i >= 0; i--){if(ratings[i] > ratings[i + 1]){right[i] = right[i + 1] + 1;}else{right[i] = 1;}}int res = 0;for(int i = 0; i < ratings.length; i++){int max = Math.max(left[i], right[i]);res += max;}return res;}
}
)
