首页 > 代码库 > leetcode第一刷_Candy

leetcode第一刷_Candy

这道题我觉得题目说的不是很明白,应该再具体举几个列子说明一下的,让我这英语渣渣的人理解偏了。。

题目的意思是,当rate比他旁边的人大时,拿的糖一定要比他多,这并不代表一样rate的人,拿到的糖要一样多。我一开始以为同样rate的人必须保证公平,思想太共产主义了。那样我的想法是按rate排名,一层一层的更新。。这个题的解法就简单多了,应该是最直接的打表。

先从左往右扫一遍,如果当前小朋友rate比左边的大,那他拿的糖就要比他多一块儿。然后再从右往左扫一遍,如果当前小朋友rate高,并且拿的糖却少,就要更新他。最后把所有的糖加起来。我觉得这里应该解释一下,从左到右扫了所有的,为什么还要从右往左再扫一遍呢?以为比较的主语对象不一样,你不比我帅,你觉得没问题,不代表我就能忍啊。那好,能不能同时比较呢?当然不能,我都没上过街,怎么知道我是不是比我的邻居要帅,光跟你比能说明问题?

ac代码如下,说一个实现的细节,都说了每人保证一块儿了嘛(出题的肯定中国人),结果就不要从0开始累计了啊,直接msize,后发的就能从0开始算了,是吧:

class Solution {
public:
    int candy(vector<int> &ratings) {
        int msize = ratings.size();
        int c[msize], res = msize;
        memset(c, 0, sizeof(c));
        for(int i=1;i<msize;i++){
            if(ratings[i]>ratings[i-1])
                c[i] = c[i-1]+1;
        }
        for(int i=msize-2;i>=0;i--){
            if(ratings[i]>ratings[i+1]&&(c[i]<=c[i+1]))
                c[i] = c[i+1]+1;
        }
        for(int i=0;i<msize;i++){
            res += c[i];
        }
        return res;
    }
};