LeetCode贪心篇

贪心算法 / 贪心思想：保证每次操作都是局部最优的，使最后得到的结果是全局最优的。

因为全局结果是局部结果的简单求和，并且局部结果互不相干，因此局部最优的策略也同样是全局最优的策略。

贪心策略

分配问题

1、排序

为了让最多的孩子吃饱，给剩余孩子里最小饥饿度的孩子分配最小的能饱腹的饼干。

2、在每次遍历中，只考虑并更新相邻一侧的大小关系

如果一个孩子的评分比自己身旁的一个孩子要高，那么这个孩子必须得到比身旁孩子更多的糖果。

3、种花

为了尽可能多地种花，从左到右遍历数组，能种花就立即种花。为了简化判断逻辑，可以在数组的开头和末尾各插入一个零（效果是一样的）。

想不到这个技巧写了一大堆判断逻辑。。。

优解：

class Solution{
    public boolean canPlaceFlowers(int[] flowerbed, int n){
        int[] a = new int[flowerbed.length + 2];
        System.arraycopy(flowerbed, 0, a, 1, flowerbed.length);
        for(int i = 1; i < a.length - 1; i++){
            if (a[[i-1] == 0 && a[i] == 0 && a[i+1] == 0){
                a[i] = 1;
                n--;
            }
        }
        return n<=0; 
    }
}

最后的判断逻辑是n<sum也就可以转换成 n - sum < 0，n减去次数就可以了。

区间问题

选择的区间结尾越小，余留给其他区间的空间就越大，就能保留更多的空间，为了移除更少个数的区间，优先保留结尾小且不相交的区间。

根据实际情况判断按区间开头排序还是按区间结尾排序。

从最小/最大开始贪心

优先考虑最小/最大的数，从小到大/从大到小贪心。