程序猿养成之路：LeetCode贪心算法典型题目 - 《LeetCode刷题笔记》

前言
贪心算法
分配问题
- LeetCode NO.455 分发饼干（简单）
- LeetCode NO.135 分发糖果（困难）
区间问题
- LeetCode NO.435 无重叠区间（中等）
练习

title: 程序猿养成之路：LeetCode贪心算法典型题目
date: 2021-02-26 22:03:55
tags:

程序猿养成之路
算法
toc: true

前言

本篇文章是阅读了高畅《LeetCode 101：和你一起你轻松刷题（C++）》之后所总结归纳的，亦借鉴了原作者的解析。

贪心算法

顾名思义，贪心算法或贪心思想采用贪心的策略，保证每次操作都是局部最优的，从而使最后得到的结果是全局最优的。
举一个最简单的例子：小明和小王喜欢吃苹果，小明可以吃五个，小王可以吃三个。已知苹果园里有吃不完的苹果，求小明和小王一共最多吃多少个苹果。在这个例子中，我们可以选用的贪心策略为，每个人吃自己能吃的最多数量的苹果，这在每个人身上都是局部最优的。又因为全局结果是局部结果的简单求和，且局部结果互不相干，因此局部最优的策略也同样是全局最优的策略。

分配问题

LeetCode NO.455 分发饼干（简单）

题目描述

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。

对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

示例 1:
输入: g = [1,2,3], s = [1,1]
输出: 1
解释:
你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
所以你应该输出1。

示例 2:
输入: g = [1,2], s = [1,2,3]
输出: 2
解释:
你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出2.

题解
因为饥饿度最小的孩子最容易吃饱，所以我们先考虑这个孩子。为了尽量使得剩下的饼干可以满足饥饿度更大的孩子，所以我们应该把大于等于这个孩子饥饿度的、且大小最小的饼干给这个孩子。满足了这个孩子之后，我们采取同样的策略，考虑剩下孩子里饥饿度最小的孩子，直到没有满足条件的饼干存在。
简而言之，这里的贪心策略是，给剩余孩子里最小饥饿度的孩子分配最小的能饱腹的饼干。至于具体实现，因为我们需要获得大小关系，一个便捷的方法就是把孩子和饼干分别排序。这样我们就可以从饥饿度最小的孩子和大小最小的饼干出发，计算有多少个对子可以满足条件。

int findContentChildren(vector<int>& g, vector<int>& s) {
    sort(g.begin(),g.end());
    sort(s.begin(),s.end());
    int i = 0, j = 0;
    while(i<g.size() && j<s.size()){
        if(g[i]<=s[j]) i++;
        j++;
    }
    return i;
    }

LeetCode NO.135 分发糖果（困难）

题目描述

老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。

你需要按照以下要求，帮助老师给这些孩子分发糖果：
每个孩子至少分配到 1 个糖果。
评分更高的孩子必须比他两侧的邻位孩子获得更多的糖果。
那么这样下来，老师至少需要准备多少颗糖果呢？

示例 1：
输入：[1,0,2]
输出：5
解释：你可以分别给这三个孩子分发 2、1、2 颗糖果。

示例 2：
输入：[1,2,2]
输出：4
解释：你可以分别给这三个孩子分发 1、2、1 颗糖果。
第三个孩子只得到 1 颗糖果，这已满足上述两个条件。

题解
我们只需要简单的两次遍历即可：把所有孩子的糖果数初始化为1；先从左往右遍历一遍，如果右边孩子的评分比左边的高，则右边孩子的糖果数更新为左边孩子的糖果数加1；再从右往左遍历一遍，如果左边孩子的评分比右边的高，且左边孩子当前的糖果数不大于右边孩子的糖果数，则左边孩子的糖果数更新为右边孩子的糖果数加1。通过这两次遍历，分配的糖果就可以满足题目要求了。这里的贪心策略即为，在每次遍历中，只考虑并更新相邻一侧的大小关系。

int candy(vector<int>& ratings) {
    int size = ratings.size();
    if(size<2) return size;
    vector<int> nums(size,1);
    for(int i = 1;i<size;i++){
        if(ratings[i-1]<ratings[i]) nums[i] = nums[i-1]+1;
    }
    for(int i = size-1;i>0;i--){
        if(ratings[i]<ratings[i-1]) nums[i-1] = max(nums[i-1],nums[i]+1);
    }
    return accumulate(nums.begin(),nums.end(),0);
}

区间问题

LeetCode NO.435 无重叠区间（中等）

题目描述

给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。

注意:
可以认为区间的终点总是大于它的起点。
区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。

示例 1:
输入: [ [1,2], [2,3], [3,4], [1,3] ]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。

示例 2:
输入: [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。

示例 3:
输入: [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间，因为它们已经是无重叠的了。

题解
在选择要保留区间时，区间的结尾十分重要：选择的区间结尾越小，余留给其它区间的空间就越大，就越能保留更多的区间。因此，我们采取的贪心策略为，优先保留结尾小且不相交的区间。
具体实现方法为，先把区间按照结尾的大小进行增序排序，每次选择结尾最小且和前一个选择的区间不重叠的区间。我们这里使用C++ 的Lambda，结合std::sort() 函数进行自定义排序。
在样例中，排序后的数组为[[1,2], [1,3], [2,4]]。按照我们的贪心策略，首先初始化为区间[1,2]；由于[1,3] 与[1,2] 相交，我们跳过该区间；由于[2,4] 与[1,2] 不相交，我们将其保留。因此最终保留的区间为[[1,2], [2,4]]。

int eraseOverlapIntervals(vector<vector<int>>& intervals) {
    if(intervals.empty()) return 0;
    sort(intervals.begin(),intervals.end(),[](vector<int> avector<int> b){return a[1]<b[1];});
    int res = 0,prev = intervals[0][1];
    for(int i = 1;i<intervals.size();i++){
        if(intervals[i][0]<prev) res++;
        else prev = intervals[i][1];
    }
    return res;
}

练习

LeetCode NO.605 种花问题（简单）

 /*将给定的数组分成三段：第一个1之前，最后一个1之后，以及两者之间。
  *··· 1 ··· ··· 1 ···
  *假设第一1的下标是l，第二个1的下标是r，数组长度为m，那么第一段内最多可种植l/2朵花，最后一段最多可种植(m-r-1)/2朵花
  *假设中间段临近两朵花的下标为i和j(j>i)，那么两者之间最多可种植(j-i-2)/2朵花。
  *根据上述规律：
  *  1. 维护prev 表示上一朵已经种植的花的下标位置，初始时prev=−1，表示尚未遇到任何已经种植的花。
  *  2. 从左往右遍历数组flowerbed，当遇到flowerbed[i]=1时根据prev和i的值计算上一个区间内可以种植花的最多数量，然后令prev=i，继续遍历数组flowerbed剩下的元素。
  *  3. 遍历数组flowerbed结束后，根据数组prev和长度mm的值计算最后一个区间内可以种植花的最多数量。
  *  判断整个花坛内可以种入的花的最多数量是否大于或等于 nn。
  */
bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        int count = 0;
        int m = flowerbed.size();
        int prev = -1;
        for (int i = 0; i < m; i++) {
            if (flowerbed[i] == 1) {
                if (prev < 0) {
                    count += i / 2;
                } else {
                    count += (i - prev - 2) / 2;
                }
                if (count >= n) {
                    return true;
                }
                prev = i;
            }
        }
        if (prev < 0) {
            count += (m + 1) / 2;
        } else {
            count += (m - prev - 1) / 2;
        }
        return count >= n;
    }

LeetCode NO.452 用最少数量的箭引爆气球（中等）

/* 和NO.435思路类似，按区间右端点升序排列，维护axis作为当前这支箭射出的位置，显然，初始时axis应该在第一个区间的右端点位置（贪心思想）。
 *判断下一区间能否被这支箭引爆(axis>points[i][0]则能引爆，否则需要多一支箭，同时更新新箭的位置)。
 */
int findMinArrowShots(vector<vector<int>>& points) {
   if(points.empty()) return 0;
   sort(points.begin(),points.end(),[&](vector<int>& a,vector<int>& b){return a[1]<b[1];});
   int axis = points[0][1];
   int count = 1;
   for(int i=1;i<points.size();i++){
       if(axis<points[i][0]){
           count++;
           axis = points[i][1];
       }
   }
   return count;
}

LeetCode NO.763 划分字母区间（中等）

/*遍历一遍数组，记录每个字母出现的最远位置。
 *重新遍历数组，len记录为当前区间最远位置，判断其他字母的最远位置是否更大，如果更大则需要更新，直到i与当前最远位置重合。接着判断其他区间。
 */
vector<int> partitionLabels(string S) {
    vector<int> last(26,-1);
    int size = S.size();
    for(int i = 0;i<size;i++){
        last[S[i]-'a'] = i;
    }
    vector<int> res;
    int len = 0;int prev = 0;
    for(int i = 0;i<size;i++){
        len = max(len,last[S[i]-'a']);
        if(len == i) {
            res.push_back(len+1-prev);
            prev = len+1;
            len = 0;
        }
    }
    return res;
}

LeetCode NO.122 买卖股票的最佳时机 II（简单）

int maxProfit(vector<int>& prices) {
    //只要股票涨了就卖
    int res = 0;
    for(int i = 1;i<prices.size();i++){
        if(prices[i]>prices[i-1]){
            res+=prices[i]-prices[i-1];
        }
    }
    return res;
}

LeetCode NO.406 根据身高重建队列（中等）

/*按照hi升序，ki降序排列队列。
 *对于最矮的人来说，他被安放好位置之后，后面需要安放的人都比他高，放在他前面，他的ki就要+1，放在他后面，他的ki不受影响。
 *因此，他的ki值就代表了他在队伍中的下标，也就是第ki+1个空位置。
 *由此我们得到了局部最优解，对第二个人来说，第一个人的位置对他没有任何影响，可以看作第一个人和他的位置不存在，他是剩下的空位置中最矮的那个，因此应该放在剩下空位置中的第ki+1个位置。
 */
vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
    sort(people.begin(),people.end(),[](vector<int>& a vector<int>& b){return a[0]<b[0] || (a[0]==b[0] && a[1]>b[1];});
    int size = people.size();
    vector<vector<int>> res(size);
    for(const vector<int>& person :people ){
        int count = person[1]+1;          //计算好这个人在队伍中的第几个位置（ki+1）
        for(int i = 0;i<size;i++){
            if(res[i].empty())  count--; //位置空的就减一，减到零的时候就找到了该位置
            if(count == 0){
                res[i] = person;
                break;
            } 

        }
    }
    return res;
}

LeetCode NO.665 非递减数列（简单）

/*
 * 4，2，3
 * -1，4，2，3
 * 2，3，3，2，4
 *我们通过分析上面三个例子可以发现，当我们发现后面的数字小于前面的数字产生冲突后，
 *[1]有时候需要修改前面较大的数字(比如前两个例子需要修改4)，
 *[2]有时候却要修改后面较小的那个数字(比如前第三个例子需要修改2)，
 *那么有什么内在规律吗？是有的，判断修改那个数字其实跟再前面一个数的大小有关系，
 *首先如果再前面的数不存在，比如例子1，4前面没有数字了，我们直接修改前面的数字为当前的数字2即可。
 *而当再前面的数字存在，并且小于当前数时，比如例子2，-1小于2，我们还是需要修改前面的数字4为当前数字2；
 *如果再前面的数大于当前数，比如例子3，3大于2，我们需要修改当前数2为前面的数3。
 */
bool checkPossibility(vector<int>& nums) {
    int n = nums.size();
    if(nums.size()<2) return true;
    int count = 0;
    for(int i=1;i<n && count<2;i++){
        if(nums[i-1]<=nums[i]) continue;
        count++;
        if( i>1 && nums[i-2] > nums[i])   nums[i] = nums[i-1];
        else nums[i-1] = nums[i];
    }
    return count <= 1;
}