代码随想录训练营23day-贪心算法

一、贪心算法

贪心算法核心思想是局部最优，以确定全局最优。当然需要使用数学归纳去总结，但是实际应用过程，可以举反例来验证是不是可以使用贪心算法。参考代码随想录

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

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

二、分发饼干

 根据贪心算法思想，题目中明确指出g[i]代表孩子的最大胃口，s[i]代表饼干的尺寸，可以思考，最大的饼干分给最大胃口的孩子，胃口小的孩子用小尺寸的饼干，这样整体上，能满足最多的孩子。

//贪心算法：局部最优，进而全局最优
void sort(int* arr, int size)
{
   for(int i = 0; i < size; i++)
   {
      for(int j = i + 1; j < size; j++)
      {
         if(arr[i] > arr[j])
         {
             int tmp = arr[i];
             arr[i] = arr[j];
             arr[j] = tmp;
         }
      }
   }
}

int findContentChildren(int* g, int gSize, int* s, int sSize) {
    
    /**排序**/
    sort(g, gSize);
    sort(s, sSize);
    
    int result = 0;
    int s_idx = sSize - 1;
    //最大的饼干s[i], 给胃口最大的孩子g[j]
    for(int i = gSize - 1; i >= 0; i--)
    {
        //g[i]的第一个是孩子的最大的胃口, s[s_idx]是最大尺寸的饼干
        if(s_idx >= 0 && g[i] <= s[s_idx])
        {  
            result++;
            s_idx--;
        }
    }
    return result;
}

还有一个思路：就是先给最小的胃口的孩子分最小尺寸的饼干，然后遍历，找到最多孩子数量。

三、摆动序列

贪心算法思路：摆动意味着左右有波动，可以考虑峰值点个数，就能判断全局最长的序列。

代码随想录上面的记录比较重要的点：1 要注意平峰时候的情况，比如单调区间，突然一段有平峰；还有类似梯形，开始有峰，然后平峰，接着递减；2 注意只有2个的情况，比如[0 0]这样的就只有一个长度序列；

int wiggleMaxLength(int* nums, int numsSize){
   if(numsSize <= 1)//numssize = 2情况，例如[0, 0]在这里不行
   {
      return numsSize;
   }
   int pre = 0, cur = 0;
   int result = 1;
   for(int i = 1; i < numsSize; i++)
   {
      cur = nums[i] - nums[i -1];
      if((pre <=0 && cur > 0) || (pre >=0 && cur < 0))
      {
        result++;
        pre = cur;
      }
   }
   return result;
}

四、最大子数组和

思路：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小 （负数加任何数都会越来越小）。

int maxSubArray(int* nums, int numsSize) {
    int result = INT_MIN;
    int sum = 0;
    if(numsSize == 0)
    {
        return 0;
    }
    for(int i = 0; i < numsSize; i++)
    { 
       sum += nums[i];
       if(sum > result)
       {
          result = sum;
       }  
       if(sum <= 0)
          sum = 0;
    }

    return result;
}