leetcode || 135、Candy
來源：程序員人生 發(fā)布時間：2015-06-09 08:33:16 閱讀次數(shù)：3485次
problem：
There are N children standing in a line. Each child is assigned a rating value.
You are giving candies to these children subjected to the following requirements:
- Each child must have at least one candy.
- Children with a higher rating get more candies than their neighbors.
What is the minimum candies you must give?
Hide Tags
Greedy
題意： 給小盆友發(fā)糖果，屬性高的糖果要更多
thinking：
（1）1道簡單的貪心題目，為什么通過率這么低？？題目中根本沒提屬性相等時怎樣發(fā)糖果。又是1道不嚴謹?shù)念}目。提交發(fā)現(xiàn)，
122的小盆友發(fā)了4個糖果，說明，第3個小盆友發(fā)了1個糖果，換做你是小盆友，你會高興嗎...
（2）撇開相等的情況不說，這道題只要處理好遞減的情況就好了。遞增或亂序好處理些
code：
class Solution{
public:
int candy(vector<int> &ratings) {
int Total = 0; /// Total candies
int length = 0; /// Continuous descending length of rate
int nPreCanCnt = 1; /// Previous child's candy count
int beforeDenc = nPreCanCnt;
if(ratings.begin() != ratings.end())
{
Total++; //Counting the first child's candy (1).
for(vector<int>::iterator i = ratings.begin()+1; i!= ratings.end(); i++)
{
if(*i < *(i⑴))
{
length++;
if(beforeDenc <= length)
{
Total++;
}
Total += length;
nPreCanCnt = 1; //This step is important, it ensures that once we leave the decending sequence, candy number start from 1
}
else
{
int curCanCnt = 0;
if(*i > *(i⑴))
{
curCanCnt = (nPreCanCnt + 1);
}
else
{
curCanCnt = 1;
}
Total += curCanCnt;
nPreCanCnt = curCanCnt;
length = 0; //reset length of decending sequence
beforeDenc = curCanCnt;
}
}
}
return Total;
}
};
生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
