贪心算法及相关例题

目录

什么是贪心算法？

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