本文主要是介绍夸父追日：第八章 贪心算法 part01，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
今日收获：理论基础，分发饼干，摆动序列，最大子序列和
1. 理论基础
思想：每一步都选择当前情况下的最优解，进而达到全局最优
2. 分发饼干
题目链接：455. 分发饼干 - 力扣（LeetCode）
思路：
（1）局部最优：把大饼干尽可能喂给大胃口的小朋友，就可以满足让更多的孩子吃饱。
（2）实现：遍历胃口数组，寻找大饼干能喂饱的第一个孩子，满足条件之后收集结果，拿下一块尽可能大的饼干。
方法：
class Solution {public int findContentChildren(int[] g, int[] s) {// 大饼干优先喂饱大胃口Arrays.sort(g);Arrays.sort(s);int result=0;// 遍历胃口值int index=s.length-1; // 饼干位移for (int i=g.length-1;i>=0;i--){// 满足条件if (index>=0&&g[i]<=s[index]){index--;result++;}}return result;}
}3. 摆动序列
题目链接：376. 摆动序列 - 力扣（LeetCode）
思路：
（1）局部最优：不断记录前后有摆动的峰值元素，忽略单调序列中的元素或者相等元素。
（2）计算一个元素和前后元素的差值，如果差值的正负不同就记录结果。如果有平坡，取平坡最右边的元素。还需要考虑三种情况：首尾元素，摆动中有平坡和单调中有平坡。
方法：
class Solution {public int wiggleMaxLength(int[] nums) {int count=1; // 默认尾元素是摆动int pre=0; // 默认首元素前面是平坡int next=0;if (nums.length==1){return 1;}// 不遍历尾元素for (int i=0;i<nums.length-1;i++){next=nums[i]-nums[i+1];// 包含摆动中有平坡的情况，选平坡最右边的元素if (pre>=0&&next<0||pre<=0&&next>0){count++;pre=next; // 只记录差值不同时的摆动方向，避免单调中有平坡的情况}}return count;}
} 总结：前面两题都是遍历数组，如果有符合条件就记录结果，并改变当下的情况。
4. 最大子序列和
题目链接：53. 最大子数组和 - 力扣（LeetCode）
思路：
（1）局部最优：判断连续和的正负，如果是负数，再加上后面的数只会让后面的数变小，不如直接从后面的数统计
（2）当前元素组成的连续和为负数时果断放弃起始元素，从其下一个元素开始统计
方法：
class Solution {public int maxSubArray(int[] nums) {int max=Integer.MIN_VALUE;int sum=0;for (int i=0;i<nums.length;i++){sum+=nums[i];max=Math.max(sum,max);// 抛弃负数的连续和if (sum<0){sum=0;continue;}}return max;}
}总结：贪心算法关键是找好局部最优的变化条件。
这篇关于夸父追日：第八章 贪心算法 part01的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
