LeedCode: Candy

https://oj.leetcode.com/problems/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?

Code [C++]

#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
    int candy(vector<int> &ratings) {
        vector<int> LeftCount(ratings.size());
        vector<int> RightCount(ratings.size());
        vector<int> Count(ratings.size());
        for (int i=0;i<ratings.size();++i){
            LeftCount[i]=1;
            RightCount[i]=1;
        }
        for (int i=0;i<ratings.size()-1;++i){
            if(ratings[i]<ratings[i+1]) LeftCount[i+1]=LeftCount[i]+1;
        }
        for (int i=ratings.size();i>0;--i){
            if(ratings[i]<ratings[i-1]) RightCount[i-1]=RightCount[i]+1;
        }
        int sum = 0;
        for(int i=0;i<ratings.size();++i){
            Count[i] =max(LeftCount[i],RightCount[i]);
            sum+=Count[i];
        }
        cout<<"Ratings: " ;
        for(int i=0;i<ratings.size();++i){
            cout<<ratings[i]<<" " ;
        }
        cout << endl;
        cout<<"Candy #: ";
        for(int i=0;i<ratings.size();++i){
            cout<<Count[i]<<" " ;
        }
        cout << endl;
        return sum;
    }
};
int main(int argc, const char * argv[]) {
    vector<int> ratings = {1,2,2,2,2,2,2,1};
    Solution mySolution;
    cout << mySolution.candy(ratings) << endl;
    return 0;
}

#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
int candy(vector<int> &ratings) {
vector<int> LeftCount(ratings.size());
vector<int> RightCount(ratings.size());
vector<int> Count(ratings.size());
for (int i=0;i<ratings.size();++i){
LeftCount[i]=1;
RightCount[i]=1;
}
for (int i=0;i<ratings.size()-1;++i){
if(ratings[i]<ratings[i+1]) LeftCount[i+1]=LeftCount[i]+1;
}
for (int i=ratings.size();i>0;–i){
if(ratings[i]<ratings[i-1]) RightCount[i-1]=RightCount[i]+1;
}
int sum = 0;
for(int i=0;i<ratings.size();++i){
Count[i] =max(LeftCount[i],RightCount[i]);
sum+=Count[i];
}
cout<<"Ratings: " ;
for(int i=0;i<ratings.size();++i){
cout<<ratings[i]<<" " ;
}
cout << endl;
cout<<"Candy #: ";
for(int i=0;i<ratings.size();++i){
cout<<Count[i]<<" " ;
}
cout << endl;
return sum;
}
};

int main(int argc, const char * argv[]) {
vector<int> ratings = {1,2,2,2,2,2,2,1};
Solution mySolution;
cout << mySolution.candy(ratings) << endl;
return 0;
}

Advertisements

About cgao

Cambridge, MA
This entry was posted in LeetCode and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s