Day31——分发饼干、摆动序列、最大子数组和（贪心）+第一天复习！

忙碌。

目录

前言

二、摆动序列

力扣

三、最大子数组和

第一天复习：

总结

---

---

前言

当生活遇到瓶颈的时候，我们不能只是等待暴风雨过去，而是要在暴风雨中学会好好地享受生活。

---

一、分发饼干

力扣


 

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

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

贪心的家长

解题思路：

为了能让更多孩子满足，所以最大的饼干应该给胃口最大的孩子（当然是给可以满足的孩子，贪得无厌的孩子不给）

我的代码：

class Solution {
public:
    
    int findContentChildren(vector<int>& g, vector<int>& s) {
        int count=0;
        sort(g.begin(),g.end());        //排好序
        sort(s.begin(),s.end());
        int leng=g.size()-1;            //长度
        int lens=s.size()-1;
        while(leng>=0&&lens>=0)
        {
            if(s[lens]>=g[leng])        //从大到小慢慢比较
            {
                lens--;        //吃了一个
                leng--;
                count++;
            }
            else                //最大的饼干给最大胃口的孩子也满足不了，索性不给他了
            {
                leng--;
            }
        }
        return count;
    }
};

二、摆动序列

力扣

解题思路：

因为可以通过删除节点来获取，那很明显把阻碍我们的元素都删掉，这样我们就可以获得最大的子序列

代码随想录图：

我们只需要删除坡点就行，也就是只是保留极值 ，可以看见，如果点两端的单调性发生变化，那么我们就可以判断它是一个极值点，可以用高度差来表示。

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if(nums.size()==0)
        {
            return 0;
        }
        int curmontain=0;        //到下一个点的高差
        int premontain=0;        //与上一个点的高差
        int ans=1;                    //默认最后一个点也有一个
        for(int i=0;isize()-1;i++)
        {
            curmontain=nums[i+1]-nums[i];        //计算到下一个点的高差
            if((curmontain>0&&premontain<=0)||(curmontain<0&&premontain>=0))//看是否改变了单调性
            {
                ans++;
                premontain=curmontain;    //更新
            }
        }
        return ans;
    }
};

---

三、最大子数组和

力扣

 有负数的结果值直接去掉不要。

class Solution {
public:
 
    int ans=INT32_MIN;            //一定要定义成最小数哇，以后icpc也要注意
    int maxSubArray(vector<int>& nums) {
        
        if(nums.size()==0)
        {
            return ans;
        }
 
        int sum=0;
        for(int i=0;isize();i++)
        {
            sum+=nums[i];                    //负的结果就直接剔除
            ans=max(ans,sum);
            if(sum<0)
            {
                sum=0;
                continue;
            }
        }
        return ans;
    }
};

第一天复习：

二分查找：不熟悉，一定要记得是左臂右闭，mid的值。

快慢指针删除数组中元素，完全忘记了，太妙了，没有找到就赋值，找到了slow停，fast++。

---

总结

感觉学了和没学一样，焦虑