1.分發(fā)餅干

455. 分發(fā)餅干

貪心的思路就是：小的餅干盡量去匹配胃口小的孩子，這樣才能實現(xiàn)盡可能多孩子吃到。

那么代碼就很好寫了：

1.排序g和s，這樣方便查找小的數(shù)

2.餅干的位置不停遍歷，對應(yīng)我們需要一個ret代表當(dāng)前孩子位置

3.如果當(dāng)前位置為孩子的數(shù)量，說明ret記錄下所有的孩子，直接返回即可。如果當(dāng)前孩子的胃口剛好小于等于餅干遍歷的位置，說明此時這個孩子是滿足要求的，那么ret++，此外，說明條件不滿足，我們需要找下一個餅干去判斷是否滿足大于或者等于小孩胃口的條件

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(),g.end());
        sort(s.begin(),s.end());
        int ret = 0;
        for(int i=0;i<s.size();i++)
        {
            if(ret==g.size())
                break;
            if(g[ret]<=s[i])
                ret++;
        }
        return ret;
    }
};

2.擺動序列

376. 擺動序列

貪心的思路：如果前一個的趨勢和后一個的趨勢一樣，那么我們就刨除掉當(dāng)前的點。這樣就能有最長的序列了

1.先介紹變量用來記錄什么：

int ret = 1：代表返回的擺動點數(shù)，由于默認一個點就是一個數(shù)，那么我們初始化就變?yōu)?

int prev = 0 ：代表前一次波動的趨勢，不過要注意的是，我們開始設(shè)置為平波動是因為第一個位置不需要比較，默認計數(shù)一次；后面prev不會用來記錄平波動，這是我用來判斷連續(xù)平波和上坡交替出現(xiàn)時的特殊點，之所以這樣設(shè)計，是讓prev代表從ret沒有變化后整體的趨勢，如果cur=0，此時不能代表前面的就一定是有起伏的，那么也就不能讓ret++。

int cur = 0：當(dāng)前位置與前一個位置的趨勢情況。

prev和cur的比較就是用來判斷ret是否加一的條件?。?/p>

2.由于第一個數(shù)（下標(biāo)為0），已經(jīng)被我們記錄下來了，那么循環(huán)的開始就從下標(biāo)1開始。先更新cur為當(dāng)前的數(shù)減去前一個數(shù)。隨后判斷此時的prev和cur條件

*由于開始我們設(shè)置的prev=0，所以此時的條件一定有一個是(prev==0&&cur!=0)，因為我們有一個條件是不能忽略的：最開始就有一個上升趨勢，那么當(dāng)前的位置是需要加一的操作才能記錄下，所以ret++

*(prev>0&&cur<0)||(prev<0&&cur>0)，那么就是一個起伏，說明當(dāng)前的趨勢和上一次趨勢是相反的，那么是可以將當(dāng)前的ret++

*上面兩個判斷都需要更新節(jié)點前一個的趨勢prev=cur；那么值得注意的是，當(dāng)cur=0時，我們不更新prev，就是條件1介紹：prev是必須要用來表示ret不變時，整體的趨勢，這樣才能判斷下一次的趨勢和整體趨勢區(qū)別，才能對ret進行操作

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int ret = 1;
        int prev = 0;
        int cur = 0;
        if(nums.size()==1)
            return ret;
        for(int i=1;i<nums.size();i++)
        {
            cur = nums[i]-nums[i-1];
            if((prev>0&&cur<0)||(prev<0&&cur>0)||(prev==0&&cur!=0))
            {
                ret++;
                prev=cur;
            }
        }
        return ret;
    }
};

3.最大子數(shù)組和

53. 最大子數(shù)組和

貪心的思路：如果累加的總數(shù)小于0，那么后面的正數(shù)會影響，也就是說下一個位置的整數(shù)并沒有起到使得總和變大的作用，那不如從下一個位置重新開始。文章來源地址http://www.zghlxwxcb.cn/news/detail-455680.html

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int ret = nums[0];
        int tmp = 0;
        for(int i=0;i<nums.size();i++)
        {
            tmp+=nums[i];
            if(ret<tmp)
                ret=tmp;
            if(tmp<0)
                tmp=0;
        }
        return ret;
    }
};

到了這里，關(guān)于【代碼隨想錄】刷題Day31的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！