贪心算法理论基础

1. 贪心算法理论基础

什么是贪心

贪心的本质是选择每一阶段的局部最优解，从而达到全局最优。

贪心的套路（什么时候用贪心）

说实话贪心算法并没有固定的套路。

所以唯一的难点就是如何通过局部最优，推出整体最优。

那么如何能看出局部最优是否能推出整体最优呢？有没有什么固定策略或者套路呢？

不好意思，也没有！ 靠自己手动模拟，如果模拟可行，就可以试一试贪心策略，如果不可行，可能需要动态规划。

有同学问了如何验证可不可以用贪心算法呢？

最好用的策略就是举反例，如果想不到反例，那么就试一试贪心吧。

贪心一般解题步骤

贪心算法一般分四步：

  • 将问题分解为若干个子问题
  • 找出适合的贪心策略
  • 求解每一个子问题的最优解
  • 将局部最优解叠成全局最优解

455.分发饼干

文章：2. 分发饼干

题目：455. 分发饼干

【思路】

  • Java实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int res = 0;
        int index = s.length-1;
        for(int i = g.length-1 ; i>=0 ;i--){
            if(index>=0 && s[index] >= g[i] ){
                index--;
                res++;
            }
        }
        return res;
    }
}
  • Go实现
1
2
3
4
5
6
7
8
9
10
11
12
func findContentChildren(g []int, s []int) int {
    sort.Ints(g)
    sort.Ints(s)
    res,index := 0,len(s)-1
    for i := len(g)-1;i >=0;i--{
        if index>=0 && s[index] >= g[i]{
            index--
            res++
        }
    }
    return res
}

376.摆动序列

文章：3. 摆动序列

题目：376. 摆动序列

【思路】

局部最优：删除单调坡度上的节点（不包括单调坡度两端的节点），那么这个坡度就可以有两个局部峰值。

整体最优：整个序列有最多的局部峰值，从而达到最长摆动序列。

实际上，我们不用进行删除的操作，只需要统计数组的峰值数量就可以了（相当于是删除单一坡度上的节点，然后统计长度）

也就是prediff > 0 && curdiff <0和prediff >0 && curdiff <0两种情况

但我们需要考虑三种情况：

1.上下坡中有平坡（考虑：prediff = 0 &&（ curdiff<0 || curdiff >0)）

2.数组首尾两端（如果数组只有两个数字，我们可以写死，如果只有两个元素，且元素不同，那么结果为2；如果不写死的话，就假设数组最前面还有一个数字，结合情况一，当相同数字连续的时候，preDiff = 0 && curdiff <0或>0 都记为波谷，那么如果数组只有两个值，就可以将{2,5}假设为{2,2,5},即prediff = 0,curdiff<0）

那么我们现在的条件限制就是：prediff >=0 && curdiff <0 || prediff <=0 && curdiff >0

3.单调坡中有平坡！！

单调中的平坡不能算峰值（摆动）

这是因为我们实时更新了prediff导致出现平坡的时候也记录了其为峰值。

因此我们应该在只有这个坡度摆动变化的时候更新prediff就好了，这样prediff在单调区间有平坡的时候就不会发送变化造成误判。

本题异常情况的本质，就是要考虑平坡， 平坡分两种，一个是 上下中间有平坡，一个是单调有平坡。

  • Java实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int wiggleMaxLength(int[] nums) {
        int prediff = 0;
        int curdiff = 0;
        int res = 1 ;//默认序列最右边有一个峰值
        for(int i = 0; i<nums.length-1;i++){
            curdiff = nums[i+1] - nums[i];
            if((prediff >=0 && curdiff <0) || (prediff <=0 && curdiff >0)){
                res++;
                prediff = curdiff;
            }
        }
        return res;
    }
}
  • Go实现
1
2
3
4
5
6
7
8
9
10
11
12
func wiggleMaxLength(nums []int) int {
    prediff ,curdiff :=0,0
    res := 1
    for  i := 0;i<len(nums)-1;i++{
        curdiff = nums[i+1] - nums[i]
        if (prediff >=0 && curdiff <0)|| (prediff <=0 && curdiff > 0){
            res++
            prediff = curdiff
        }
    }
    return res
}

53.最大子序和

文章：

题目：

【思路】

  • Java实现
1

  • Go实现
1

【算法总结】

  • 分发饼干：使用贪心，将胃口和饼干数都进行排序，然后从后往前遍历胃口，判断饼干的饱腹值是否符合小孩胃口，符合就饼干的索引–
  • 摆动序列：使用贪心，需要分析两种特殊情况：第一种是平坡（上下平坡，单调值平坡（在出现坡度变化的时候才修改prediff值）），第二种是数组只有两个值（默认左右边有1个峰值）的情况