z*********8
发帖数: 2070 | 1 Candy AC Rate: 25/267 My Submissions
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?
大家讨论一下 |
l****o
发帖数: 315 | 2 刚秒完。。。这道还是很容易吧。从头到尾从尾到头各扫一遍就可以了。空间O(n)时间
O(n)。期待更优解。 |
c**d
发帖数: 580 | 3 find out all local min rating,
for each local min rating, start with 1 candy, and expand on both directions
until hit by local max.
return total candies.
O(n)
【在 z*********8 的大作中提到】
: Candy AC Rate: 25/267 My Submissions
: 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?
: 大家讨论一下
|
z*********8
发帖数: 2070 | 4 怎么扫啊
【在 l****o 的大作中提到】
: 刚秒完。。。这道还是很容易吧。从头到尾从尾到头各扫一遍就可以了。空间O(n)时间
: O(n)。期待更优解。
|
l****o
发帖数: 315 | 5 public class Solution {
public int candy(int[] ratings) {
// Note: The Solution object is instantiated only once and is reused
by each test case.
int rLen = ratings.length;
if (rLen == 0) return 0;
int min = rLen; int give = 0;
int[] gives = new int[rLen];
for (int i = 1; i < rLen; i++) {
if (ratings[i] > ratings[i - 1]) give++;
else give = 0;
gives[i] = give;
}
give = 0;
for (int i = rLen - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) give++;
else give = 0;
min += Math.max(give, gives[i]);
}
min += gives[rLen - 1];
return min;
}
}
三楼说的方法好像可以省空间。你可以试试。
【在 z*********8 的大作中提到】
: 怎么扫啊
|
f*****h
发帖数: 10 | 6 1-pass linear scan
O(1) extra space |
z*********8
发帖数: 2070 | 7 more details pls?
【在 f*****h 的大作中提到】
: 1-pass linear scan
: O(1) extra space
|
f*****h
发帖数: 10 | 8 Hint:
Group the babies by their ratings as longest decreasing groups, for example
4 3 2 3 2 1 2 3 4 4 5 5
->
(4 3 2) (3 2 1) (2) (3) (4) (4) (5) (5)
The total candies for a group of size N contains two parts
i) max(N, candy_of_last_baby_in_last_group + 1) (*)
ii) N-1 + N-2 + ... + 1
(*) There is a corner case here.
【在 z*********8 的大作中提到】
: more details pls?
|
|
d*k
发帖数: 207 | 9 一直用old oj，没发现多了三道题目，仔细一看居然来自flexme的中文OJ。
再次赞flexme大牛。
【在 z*********8 的大作中提到】
: Candy AC Rate: 25/267 My Submissions
: 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?
: 大家讨论一下
|
b******7
发帖数: 92 | 10 给了个笨方法，也过了oj。构造图，利用拓扑排序计算
class Solution {
public:
int candy(vector &ratings) {
// Note: The Solution object is instantiated only once and is reused
by each test case.
if(ratings.empty()){
return 0;
}
if(ratings.size() == 1){
return 1;
}
int sum = 0;
int n = ratings.size();
vector candy(n, 1);
vector indegree(n, 0);
vector > edges(n, vector());
for(int i = 1; i < ratings.size(); i++){
//[i-1, i]
if(ratings[i-1] < ratings[i]){
edges[i-1].push_back(i);
indegree[i] ++;
}else if(ratings[i-1] > ratings[i]){
edges[i].push_back(i-1);
indegree[i-1]++;
}
}
queue q;
for(int i = 0; i < n; i++ ){
if(indegree[i] == 0){
q.push(i);
}
}
while(!q.empty()){
int cur = q.front();
q.pop();
sum += candy[cur];
for(int i : edges[cur]){
indegree[i]--;
if(indegree[i] == 0){
q.push(i);
}
candy[i] = candy[cur] + 1;
}
}
return sum;
}
}; |
|
|
a******e
发帖数: 710 | 11 1 2 3 4 5 6 7这种情况怎么解？
example
【在 f*****h 的大作中提到】
: Hint:
: Group the babies by their ratings as longest decreasing groups, for example
: 4 3 2 3 2 1 2 3 4 4 5 5
: ->
: (4 3 2) (3 2 1) (2) (3) (4) (4) (5) (5)
: The total candies for a group of size N contains two parts
: i) max(N, candy_of_last_baby_in_last_group + 1) (*)
: ii) N-1 + N-2 + ... + 1
: (*) There is a corner case here.
|
g*******9
发帖数: 32 | 12 从左往右找递增子区间，记录每个子区间最小值，从最小值开始给糖果，从1开始，依
次加1；从右往左，从每个最小值向左扫，给没有糖果的。应该是O(n) |
q******5
发帖数: 10 | 13 可能我没有读懂题：Children with a higher rating get more candies than their
neighbors.
input [2,2,1] 怎么可能4个candy就够了？
这三个小孩分别得到多少candy？
谢。
【在 z*********8 的大作中提到】
: Candy AC Rate: 25/267 My Submissions
: 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?
: 大家讨论一下
|
p*********y
发帖数: 17 | 14 题目的意思是一样RATING的孩子可以得到不同数量的candy，这里就是[2,1,1]
their
【在 q******5 的大作中提到】
: 可能我没有读懂题：Children with a higher rating get more candies than their
: neighbors.
: input [2,2,1] 怎么可能4个candy就够了？
: 这三个小孩分别得到多少candy？
: 谢。
|
P*******r
发帖数: 210 | 15 我觉得rating 是 【2，2，1】的话， 分法可以是[1,2,1]。
第一遍coding 的时候，也是这个case错掉了。
【在 p*********y 的大作中提到】
: 题目的意思是一样RATING的孩子可以得到不同数量的candy，这里就是[2,1,1]
:
: their
|
P*******r
发帖数: 210 | 16 我觉得rating 是 【2，2，1】的话， 分法可以是[1,2,1]。
第一遍coding 的时候，也是这个case错掉了。
【在 p*********y 的大作中提到】
: 题目的意思是一样RATING的孩子可以得到不同数量的candy，这里就是[2,1,1]
:
: their
|
a******e
发帖数: 710 | 17 糖果数为1,2,1
如果两个小孩rating相同，没有规定他们的糖果数要如何。
their
【在 q******5 的大作中提到】
: 可能我没有读懂题：Children with a higher rating get more candies than their
: neighbors.
: input [2,2,1] 怎么可能4个candy就够了？
: 这三个小孩分别得到多少candy？
: 谢。
|
c********p
发帖数: 1969 | |
l****o
发帖数: 315 | 19 这种做法我之前试了，边界条件总是想不清。Can you show me the code?
example
【在 f*****h 的大作中提到】
: Hint:
: Group the babies by their ratings as longest decreasing groups, for example
: 4 3 2 3 2 1 2 3 4 4 5 5
: ->
: (4 3 2) (3 2 1) (2) (3) (4) (4) (5) (5)
: The total candies for a group of size N contains two parts
: i) max(N, candy_of_last_baby_in_last_group + 1) (*)
: ii) N-1 + N-2 + ... + 1
: (*) There is a corner case here.
|
b***e
发帖数: 1419 | 20 /*
Here's a solution with JS, O(n) time and O(1) space.
You can copy&paste the full body of this post and run it in
a browser console.
*/
var minCandies = function(children) {
var maxHeight = children.length;
var state = 'desc';
var height = maxHeight;
var accumulated = 0;
var count = 0;
for (var i = 0; i < children.length - 1; i++) {
accumulated += height;
count++;
if (state == 'desc') {
if (a[i] > a[i+1]) {
height--;
} else if (a[i] == a[i+1]) {
} else {
var diff = height - 1;
accumulated -= diff * count;
count = 0;
height = 2;
state = 'asc';
}
}
else { // state == 'asc'
if (a[i] < a[i+1]) {
height++;
} else if (a[i] == a[i+1]) {
} else {
count = 0;
height = maxHeight;
state = 'desc';
}
}
}
// handle the last child
if (state == 'desc') {
accumulated += height;
count++;
var diff = height - 1;
accumulated -= diff * count;
} else {
accumulated += height;
}
return accumulated;
};
// var a = [1,2,3,4,5,6,7];
// var a = [100,99,98,97,96,95,94];
var a = [4,3,2,3,2,1,2,3,4,4,5,5];
// 3,2,1,3,2,1,2,3,4,4,5,5
console.log(minCandies(a)); |
l*****0
发帖数: 13 | 21 class Solution {
public:
bool getSum(vector &ratings, int &sum)
{
bool isReverse = false;
int n = ratings.size();
int* candy = new int[n];
memset(candy, 0, n*sizeof(int));
candy[0] = 1;
for (int i=1; i
{
if (ratings[i] > ratings[i-1])
candy[i] = candy[i-1] + 1;
else if (ratings[i] == ratings[i-1])
candy[i] = candy[i-1];
else
{
isReverse = true;
candy[i] = 1;
if (candy[i-1] == 1)
{
candy[i-1]++;
int j=i-1;
while (j>=1 && ratings[j-1] > ratings[j] && candy[j-1] <
= candy[j])
{
candy[j-1]++;
j--;
}
}
}
}
for (int i=0; i
sum += candy[i];
return isReverse;
}
int candy(vector &ratings) {
// Note: The Solution object is instantiated only once and is reused
by each test case.
int sum1 = 0;
bool isReverse = getSum(ratings, sum1);
if (!isReverse)
return sum1;
int n = ratings.size();
for (int i=0, j=n-1; i
{
int tmp = ratings[i];
ratings[i] = ratings[j];
ratings[j] = tmp;
}
int sum2 = 0;
getSum(ratings, sum2);
return sum1
}
}; |
l*****0
发帖数: 13 | 22 class Solution {
public:
bool getSum(vector &ratings, int &sum)
{
bool isReverse = false;
int n = ratings.size();
int* candy = new int[n];
memset(candy, 0, n*sizeof(int));
candy[0] = 1;
for (int i=1; i
{
if (ratings[i] > ratings[i-1])
candy[i] = candy[i-1] + 1;
else if (ratings[i] == ratings[i-1])
candy[i] = candy[i-1];
else
{
isReverse = true;
candy[i] = 1;
if (candy[i-1] == 1)
{
candy[i-1]++;
int j=i-1;
while (j>=1 && ratings[j-1] > ratings[j] && candy[j-1] <
= candy[j])
{
candy[j-1]++;
j--;
}
}
}
}
for (int i=0; i
sum += candy[i];
return isReverse;
}
int candy(vector &ratings) {
// Note: The Solution object is instantiated only once and is reused
by each test case.
int sum1 = 0;
bool isReverse = getSum(ratings, sum1);
if (!isReverse)
return sum1;
int n = ratings.size();
for (int i=0, j=n-1; i
{
int tmp = ratings[i];
ratings[i] = ratings[j];
ratings[j] = tmp;
}
int sum2 = 0;
getSum(ratings, sum2);
return sum1
}
}; |
