首页 > 代码库 > Candy
Candy
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?
思路：使用先递增后递减的规则遍历输入数组。递增过程中，每次给的糖果数从2增加到n；递减过程中，每次给的糖果数从1增加到m。若m+1>n，则说明递增序列与递减序列中间的最大值应该给m+1个，而实际我们只给了n个，因此应该在总糖果数上加上m-n+1。
1 class Solution { 2 public: 3 int candy( vector<int> &ratings ) { 4 if( ratings.size() <= 1 ) { return ratings.size(); } 5 int prev = 1, i = 1, n_candy = 1, size = ratings.size(); 6 while( i < size ) { 7 int num = 1; 8 while( i < size && ratings[i] > ratings[i-1] ) { n_candy += ++num; ++i; } 9 if( num != 1 ) { prev = num; }10 num = 0;11 while( i < size && ratings[i] < ratings[i-1] ) { n_candy += ++num; ++i; }12 if( num+1 > prev ) { n_candy += num-prev+1; }13 if( i < size && ratings[i] == ratings[i-1] ) { ++n_candy; ++i; prev = 1; }14 }15 return n_candy;16 }17 };
另一种方法通过依次向前、向后遍历确定每个child分配到的糖果的数目。向前遍历时，若序列递增（即ratings[i]<ratings[i+1]），则将分配的糖果数加1；向后遍历时，若序列递减（即ratings[i]>ratings[i+1]），则将分配的糖果数加1。注意：向后遍历时，当前的糖果数应该取向前遍历结果和向后遍历结果中的较大值。
1 class Solution { 2 public: 3 int candy( vector<int> &ratings ) { 4 if( ratings.size() <= 1 ) { return ratings.size(); } 5 int size = ratings.size(); 6 vector<int> n_candy( size, 1 ); 7 for( int i = 1; i < size; ++i ) { 8 if( ratings[i] > ratings[i-1] ) { 9 n_candy[i] = n_candy[i-1] + 1;10 }11 }12 for( int i = size-2; i >= 0; --i ) {13 if( ratings[i] > ratings[i+1] && n_candy[i] < n_candy[i+1] + 1 ) {14 n_candy[i] = n_candy[i+1] + 1;15 }16 }17 int sum = 0;18 for( int i = 0; i < size; ++i ) { sum += n_candy[i]; }19 return sum;20 }21 };
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。