贪心算法基础及leetcode例题

理论

本质:找到每个阶段的局部最优,然后去推导得到全局最优
两个极端:常识&&很难:

很多同学通过了贪心的题目,但都不知道自己用了贪心算法,因为贪心有时候就是常识性的推导,所以会认为本应该就这么做!

套路:
贪心没有套路,说白了就是常识性推导加上举反例
做题的时候,只要想清楚 局部最优 是什么,如果推导出全局最优,其实就够了。

贪心算法一般分为如下四步:

将问题分解为若干个子问题
找出适合的贪心策略
求解每一个子问题的最优解
将局部最优解堆叠成全局最优解
这个四步其实过于理论化了,我们平时在做贪心类的题目 很难去按照这四步去思考,真是有点“鸡肋”。

Leetcode题目

简单题

455.分发饼干

思路:大饼干 喂 胃口大的kid,才能充分利用

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int j=s.length-1;
        int sum = 0;

        for(int i=g.length-1;i>=0;i--){
            if(j>=0 && s[j]>=g[i]){
                sum++;
                j--;
            }
        }
        return sum;
    }
}

中等题

序列问题---376. 摆动序列

股票问题---122. 买卖股票的最佳时机 II

两个维度权衡问题---135. 分发糖果

热门相关:地球第一剑   薄先生,情不由己   网游之逆天飞扬   霸皇纪   网游之逆天飞扬