算法训练day31|贪心算法part1

2023-12-16 14:25:42

理论基础:

贪心算法没有模版

通过找到局部最优解来获得全剧最优解

455.分发饼干

大饼干给大胃口

先遍历胃口再遍历饼干

小饼干给小需求

先遍历饼干,再遍历胃口

376. 摆动序列

局部最优:同一趋势下,只用管最大值和最小值,

全剧最优:整个序列有最多的局部峰值,从而达到最长摆动序列

  1. 情况一:上下坡中有平坡
  2. 情况二:数组首尾两端
  3. 情况三:单调坡中有平坡

为了应对情况1,我们只计入平->摆的部分?所以我们记录峰值的条件应该是:?(preDiff <= 0 && curDiff > 0) || (preDiff >= 0 && curDiff < 0)

为了应对情况2,

prevdiff初始值为0,这样会记录右边的端点(至少有两个值的时候)

result 初始化为1,默认记录了左边的端点

nums数量小于2的时候直接返回nums.length

为了应对情况3,我们只在有峰值记录的时候才记录prevdiff,prevdiff更像是记录之前的整体趋势的

动态规划

For every position in the array, there are only three possible statuses for it.

  • up position, it means nums[i] > nums[i-1]
  • down position, it means nums[i] < nums[i-1]
  • equals to position, nums[i] == nums[i-1]

So we can use two arrays up[] and down[] to record?the max wiggle sequence length so far?at index?i.
If nums[i] > nums[i-1], that means it wiggles up. the element before it must be a down position. so up[i] = down[i-1] + 1; down[i] keeps the same with before.
If nums[i] < nums[i-1], that means it wiggles down. the element before it must be a up position. so down[i] = up[i-1] + 1; up[i] keeps the same with before.
If nums[i] == nums[i-1], that means it will not change anything becasue it didn't wiggle at all. so both down[i] and up[i] keep the same.

In fact, we can reduce the space complexity to O(1), but current way is more easy to understanding.

public class Solution {
    public int wiggleMaxLength(int[] nums) {
        
        if( nums.length == 0 ) return 0;
        
        int[] up = new int[nums.length];
        int[] down = new int[nums.length];
        
        up[0] = 1;
        down[0] = 1;
        
        for(int i = 1 ; i < nums.length; i++){
            if( nums[i] > nums[i-1] ){
                up[i] = down[i-1]+1;
                down[i] = down[i-1];
            }else if( nums[i] < nums[i-1]){
                down[i] = up[i-1]+1;
                up[i] = up[i-1];
            }else{
                down[i] = down[i-1];
                up[i] = up[i-1];
            }
        }
        
        return Math.max(down[nums.length-1],up[nums.length-1]);
    }
}

53. 最大子序和

如果前面的连续和为负数就立刻放弃

用这次的nums[i]作为连续和第一个数

一直记录连续和的最大值

文章来源:https://blog.csdn.net/AdrianLeon/article/details/134937643
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。