leetcode刷题day27|贪默算法Part01（455.分发饼干、376. 摆动序列、53. 最大子序和）

前言： 贪婪的本质选择每一阶段的局部最优，从而到达全局最优。
455.分发饼干

思绪：局部最优-大饼干喂给胃口大的，充实使用饼干尺寸喂饱一个；全局最优：喂饱尽大概多的小孩。可以实验使用贪婪计谋，先将饼干数组和小孩数组排序，然后从后向前遍历小孩数组，用大饼干优先满足胃口大的，并统计满足小孩数量。具体实现使用两个指针分别指向两个数组，最大的饼干能满足胃口最大的小孩，小孩数量加一，两个指针同时前移，假如最大的饼干不能满足，则小孩指针前移，继承判定。
代码如下：

1. class Solution {
2.     public int findContentChildren(int[] g, int[] s) {
3.         Arrays.sort(g);
4.         Arrays.sort(s);
5.         int sNum=s.length-1;
6.         int child=0;
7.         for(int i=g.length-1;i>=0;i--){
8.             if(sNum>=0 && g[i]<=s[sNum]){
9.                 child++;
10.                 sNum--;
11.             }
12.         }
13.         return child;
14.     }
15. }

复制代码

留意：假如是想先喂饱大胃口的小孩，for循环只能是胃口，用下标控制饼干，如许才气满足条件时才移动饼干。
376. 摆动序列

思绪：
局部最优：删除单调坡度上的节点（不包罗单调坡度两头的节点），那么这个坡度就可以有两个局部峰值。
团体最优：整个序列有最多的局部峰值，从而到达最长摆动序列。
实际利用可以不做删除利用，标题要求最长摆动子序列的长度，只必要统计数组的峰值数量即可。
思量三种特别环境：
环境一：上下坡中有平坡：这个时间必要思量生存平坡左端点还是右端点，假如生存左端点即答应prediff==0。
环境二：数组首尾两头：只有两个元素时，result 初始为 1（默认最右面有一个峰值），此时 curDiff > 0 && preDiff <= 0，那么 result++（盘算了左面的峰值），末了得到的 result 就是 2（峰值个数为 2 即摆动序列长度为 2）
环境三：单调坡中有平坡：设置只有在峰值处将curDiff 赋值给preDiff。
代码如下：

1. class Solution {
2.     public int wiggleMaxLength(int[] nums) {
3.         int result=1;
4.         int preDiff=0;
5.         int curDiff=0;
6.         for(int i=1;i<nums.length;i++){
7.             curDiff=nums[i]-nums[i-1];
8.             if((preDiff<=0 && curDiff>0 )||(preDiff>=0 && curDiff<0)){
9.                 result++;
10.                 preDiff=curDiff;
11.             }
12.         }
13.         return result;
14.     }
15. }

复制代码

53. 最大子序和

思绪：局部最优：当前“连续和”为负数的时间立即放弃，从下一个元素重新盘算“连续和”，由于负数加上下一个元素 “连续和”只会越来越小。
全局最优：选取最大“连续和”
代码如下：

1. class Solution {
2.     public int maxSubArray(int[] nums) {
3.         int result=Integer.MIN_VALUE;
4.         int sum=0;
5.         for(int i=0;i<nums.length;i++){
6.             sum+=nums[i];
7.             result=Math.max(result,sum);
8.             if(sum<=0){
9.                 sum=0;
10.             }
11.         }
12.         return result;
13.     }
14. }

复制代码

留意只有负数的环境。
总结：现在来看贪默算法的代码并不难，但是难在想到什么是局部最优？怎么到达局部最优？