首页 > 代码库 > 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; } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。