Repository navigation
Expand file tree
/
Copy pathcandy.cpp
More file actions
106 lines (95 loc) · 2.99 KB
/
Copy pathcandy.cpp
File metadata and controls
106 lines (95 loc) · 2.99 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
// Source : https://oj.leetcode.com/problems/candy/
// Author : Hao Chen
// Date : 2014-10-12
/**********************************************************************************
*
* 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?
*
*
**********************************************************************************/
#include <stdlib.h>
#include <time.h>
#include <iostream>
#include <vector>
using namespace std;
void print(vector<int> &v);
/*
* The soluiton is O(2n) run-time complexity
*
* For example:
*
* ratings[] = { 5, 6, 7, 4, 1, 2, 3, 2, 1, 7 }
*
* 1) Go through the ratings from left to right.
*
* Find the each increasing sub-array, giving the minimal candy
*
* ratings[] = { 5, 6, 7, 4, 1, 2, 3, 2, 1, 7 }
* ------> -> ------> -> --->
* candy[] = { 1, 2, 3, 1, 1, 2, 3, 1, 1, 2 }
*
* 2) Go through the raings from right to left.
*
* ratings[] = { 5, 6, 7, 4, 1, 2, 3, 2, 1, 7 }
* <- <- <------ <- <------ <-
* prev_candy[] = { 1, 2, 3, 1, 1, 2, 3, 1, 1, 2 }
* +1 +1
* candy[] = { 1, 2, 3, 2, 1, 2, 3, 2, 1, 2 }
*
* 3) total candy is 19
*
*/
int candy(vector<int> &ratings) {
vector<int> candyCnt(ratings.size()) ;
//allocate candies, considering the minimal rating on the left
candyCnt[0] = 1;
for(int i = 1; i < ratings.size(); i++){
candyCnt[i] = ratings[i] > ratings[i-1] ? candyCnt[i-1]+1 : 1;
}
print(candyCnt);
//modify the allocation, considering the minimal rating on the right
int totalCandy = candyCnt[ratings.size()-1];
for(int i = ratings.size()-2; i >= 0; i--){
candyCnt[i] = (ratings[i] > ratings[i+1] && candyCnt[i+1]+1 > candyCnt[i]) ? candyCnt[i+1]+1 : candyCnt[i];
//count total candies by the way
totalCandy += candyCnt[i];
}
print(candyCnt);
return totalCandy;
}
void generateRatings(vector<int> &ratings, int n) {
srand(time(0));
for (int i=0; i<n; i++) {
ratings.push_back(rand()%10);
}
}
void print(vector<int> &v) {
for(int i=0; i<v.size(); i++){
cout << v[i] << " ";
}
cout << endl;
}
int main(int argc, char**argv)
{
int n = 10;
if (argc>1){
n = atoi(argv[1]);
}
vector<int> ratings;
generateRatings(ratings, n);
print(ratings);
cout << candy(ratings) << endl;
cout << "--------------------" << endl;
int r[] = { 5, 6, 7, 4, 1, 2, 3, 2, 1, 7 };
vector<int> ra(r, r+sizeof(r)/sizeof(r[0]));
print(ra);
cout << candy(ra) << endl;
return 0;
}