有N个小朋友站在一排，每个小朋友都有一个评分
你现在要按以下的规则给孩子们分糖果：
- 每个小朋友至少要分得一颗糖果
- 分数高的小朋友要他比旁边得分低的小朋友分得的糖果多
你最少要分发多少颗糖果？
[编程题]分糖果
class Solution {
public:
int candy(vector<int> &ratings) {
//题意：N个孩子站成一排，每个孩子分配一个分值。给这些孩子派发糖果，满足如下要求：
//每个孩子至少一个
//分值更高的孩子比他的相邻位的孩子获得更多的糖果
//求至少分发多少糖果？
int len=ratings.size();
if(len==1) return 1;
int sum=0;
vector<int> v(len,1);//初始将每个孩子的糖果数都设为1
//从左向右扫描，保证一个方向上分数更大的糖果更多
for(int i=1;i<len;i++){
if(ratings[i] > ratings[i-1])
v[i]=v[i-1]+1;
}
//从右向左扫描，保证另一个方向上分数更大的糖果更多
for(int i=len-2;i>=0;i--){
if(ratings[i] > ratings[i+1] && v[i] <= v[i+1])
v[i]=v[i+1]+1;
}
for(int i=0;i<len;i++){
sum+=v[i];
}
return sum;
}
};
发表于 2016-09-12 00:34:44
回复(10)
class Solution {
public:
/*
遍历两边，首先每个人得一块糖，第一遍从左到右，若当前点比前一个点高就比前者多一块。
这样保证了在一个方向上满足了要求。第二遍从右往左，若左右两点，左侧高于右侧，但
左侧的糖果数不多于右侧，则左侧糖果数等于右侧糖果数+1，这就保证了另一个方向上满足要求
*/
int candy(vector<int> &ratings)
{
int n = ratings.size();
if(n==0) return 0;
vector<int> candy(n,1);
for(int i=1;i<n;i++)
{
if(ratings[i] > ratings[i-1])
candy[i] = candy[i-1]+1;
}
for(int i=n-1;i>=0;i--)
{
if(ratings[i-1] > ratings[i] && candy[i-1] <= candy[i])
candy[i-1] = candy[i]+1;
}
return accumulate(candy.begin(),candy.end(),0);
}
};
发表于 2017-07-06 14:49:47
回复(1)
正向一次 反向一次ok了
class Solution {
public:
int candy(vector<int> &ratings) {
int n = ratings.size();
int *dp = new int[n], sum = 0;
for(int i=0;i<n;i++) dp[i] = 1;
for(int i=1;i<n;i++)
if(ratings[i] > ratings[i-1])
dp[i] = dp[i-1] + 1;
for(int i=n-1;i>0;i--)
if(ratings[i-1] > ratings[i] && dp[i-1] <= dp[i])
dp[i-1] = dp[i] + 1;
for(int i=0;i<n;i++) sum += dp[i];
return sum;
}
};
发表于 2019-04-13 16:40:01
回复(0)
import java.util.*;
public class Solution {
public int candy(int[] ratings) {
if(ratings==null || ratings.length==0) {
return 0;
}
int[] count = new int[ratings.length];
//每个孩子初始都有一个糖果
Arrays.fill(count,1);
int sum = 0;
for(int i=1;i<ratings.length;i++) {
if(ratings[i]>ratings[i-1]) {
count[i] = count[i-1]+1;
}
}
for(int i=ratings.length-1;i>0;i--) {
sum+=count[i];
if(ratings[i]<ratings[i-1] && count[i]>=count[i-1]) {
count[i-1] = count[i]+1;
}
}
sum+=count[0];
return sum;
}
}
发表于 2016-03-19 15:56:08
回复(11)
import java.util.Arrays;
public class Solution { //状态转移方程为 candies[i] = max{candies[i-1], candies[i+1]} + 1
public int candy(int[] ratings) {
int sum = 0;
int [] candies = new int [ratings.length];
Arrays.fill(candies, 1);//把糖果数组初始化为1
//从左向右使得当ratings[i] > ratings[i-1]时，candies[i] > candies[i-1]
for(int i = 1; i < ratings.length; i++) {
if(ratings[i] > ratings[i-1])
candies[i] = Math.max(candies[i], candies[i-1] + 1);
}
//从右向左扫描，使得ratings[i] > ratings[i+1]时，candies[i] > candies[i+1]
sum += candies[candies.length-1];
for(int i = ratings.length-2; i >= 0; i--) {
if(ratings[i] > ratings[i+1])
candies[i] = Math.max(candies[i], candies[i+1] + 1);
sum += candies[i];
}
return sum;
}
}
发表于 2017-12-06 13:03:05
回复(0)
（1）笨方法
动态规划思想（易于理解）：每个糖果的值都要受限与邻居结点（如果评估值比邻居结点大，那么得到的糖果也比邻居结点多）
- 根据限制我们可以想到一个二维数组，从初次扫描开始，每次扫描将评估值与同行前一个结点和前一行后一个结点的值比较，如果大于就加一。
- 何时结束：N个值，最多进行N次循环，因为最多N个不同的数，最大糖果差为N。
本题，使用NN的数组会超出内存限制，于是改用2N的数组，其实，也只用到两行，前一行，后一行。
int candy(vector<int> &ratings) {
vector<vector<int>> v(2,vector<int>());
for(int i = 0;i < ratings.size();i++){
v[0].push_back(0);
v[1].push_back(0);
}
//初始化，每个孩子一个糖果
for(int i = 0;i < ratings.size();i++)
v[0][i] = 1;
bool bc = true;
bool inturn = true;
int pre,pos;
for(int i = 1;i < ratings.size();i++){
if(!bc) break;
bc = false;
//轮流切换两行
if(inturn){
pre = 0;
pos = 1;
inturn = false;
} else{
pre = 1;
pos = 0;
inturn = true;
}
//与左邻居和右邻居比较
for(int j = 0;j < ratings.size();j++){
v[pos][j] = v[pre][j];
if(j>0){
if(ratings[j] > ratings[j-1]){
if(v[pre][j] <= v[pos][j-1]){
v[pos][j] = v[pos][j-1] + 1;
if(!bc) bc = true;
}
}
}
if(j<ratings.size()-1){
if(ratings[j] > ratings[j+1]){
if(v[pos][j] <= v[pre][j+1]){
v[pos][j] = v[pre][j+1] + 1;
if(!bc) bc = true;
}
}
}
}
}
int minCan = 0;
if(inturn) pos = 0;
else pos = 1;
for(int i = 0;i < ratings.size();i++)
minCan += v[pos][i];
return minCan;
}
（2）灵活方法
第一次从左向右扫描找到一个方向上的最大值，第二次从右向左扫描找到另一个方向的最大值。
- 从左向右扫描后能保证比左边邻居大1
- 从右向左扫描后能保证比右边邻居大1，同时因为第一次扫描，也可以保证比左边大1
为什么还要从右向左扫描，因为有可能右边邻居等于自身。
例如：2 1
输出应该为 3，只从左向右的，会输出2
同步博客int candy(vector<int> &ratings) { int n = ratings.size(); vector<int> v(n,1); for( int i = 1;i < n;i++) if(ratings[i]>ratings[i-1]) v[i] = v[i-1]+1; int sum = 0; for( int i = n-1;i > 0;i--){ if(ratings[i-1]>ratings[i]&&v[i-1]<=v[i]) v[i-1] = v[i] + 1; sum += v[i]; } sum += v[0]; return sum; }
发表于 2017-11-28 15:29:36
回复(1)
dp做法：
class Solution {
public:
int candy(vector<int> &ratings) {
int r=ratings.size();
map<int,int> mp;mp.clear();
for(int i=0;i<r;i++) mp[i]=1;
for(int i=0;i<r-1;i++){
if(ratings[i]<ratings[i+1])
mp[i+1]=mp[i]+1;
}
int ans=0;
for(int i=r-2;i>=0;i--)
if(ratings[i]>ratings[i+1])
mp[i]=max(mp[i],mp[i+1]+1);
for(int i=0;i<r;i++) ans+=mp[i];
return ans;
}
};
拓扑排序做法（果然我dp还是弱到爆）
class Solution {
public:
int candy(vector<int> &ratings) {
queue<int> q;
vector<int> G[100000];
int ans=0,r=ratings.size(),indeg[100000],dp[100000];
memset(indeg,0,sizeof(indeg));
memset(dp,0,sizeof(dp));
for(int i=0;i<r-1;i++){
if(ratings[i]>ratings[i+1]) indeg[i]++,G[i+1].push_back(i);
else if(ratings[i]<ratings[i+1]) indeg[i+1]++,G[i].push_back(i+1);
}
for(int i=0;i<r;i++) if(!indeg[i]) dp[i]=1,q.push(i);
while(q.size()){
int u=q.front();q.pop();
for(int j=0;j<G[u].size();j++){
int v=G[u][j];
dp[v]=max(dp[v],dp[u]+1);
indeg[v]--;
if(!indeg[v]) q.push(v);
}
}
for(int i=0;i<r;i++) ans+=dp[i];
return ans;
}
};
编辑于 2017-04-14 13:29:43
回复(0)
先从左到右，再从右到左扫描两遍即可
public class Solution {
public int candy(int[] ratings) {
if(ratings == null || ratings.length <= 1)
return 1;
int[] candy = new int[ratings.length];
int sum = 0;
for(int i = 0; i < candy.length; i++)
candy[i] = 1;
for(int i = 1; i < candy.length; i++){
if(ratings[i] > ratings[i - 1])
candy[i] = candy[i - 1] + 1;
}
for(int i = candy.length - 1; i > 0; i--){
if(ratings[i] < ratings[i - 1] && candy[i] >= candy[i - 1])
candy[i - 1] = candy[i] + 1;
}
for(int i = 0; i < candy.length; i++)
sum += candy[i];
return sum;
}
}
发表于 2017-05-15 16:35:55
回复(0)
分享个别的思路，用左右指针，使每次得到局部最优。基本思路就是分数高的在分数低的基础上加一块糖，分数一样或者低的就先只拿一块糖，后面根据指针按需补足。
class Solution {
public:
/**
*
* @param ratings int整型vector
* @return int整型
*/
int candy(vector<int>& ratings) {
// write code here
int res = 1, pointer = 0, tmp=1, count =0;
for (int i=1; i!=ratings.size(); ++i){
if (ratings[i]>ratings[i-1]){
pointer = i; //指针
if (count != 0) tmp = 1;
tmp++; //tmp用于存储当前指针所指向的小朋友分到的糖果数量
res += tmp;
count =0;
}
else if(ratings[i]==ratings[i-1]){
pointer = i;
tmp=1;
res += tmp;
count =0;
}
else{
res += i-pointer+1; //分数下降，则不移动指针，给指针到当前小朋友每人加一颗糖
count ++;
if (tmp>count) res --;
}
}
return res;
}
};
发表于 2022-01-09 07:28:55
回复(0)
public class Solution {
public int candy(int[] ratings) {
if(ratings == null || ratings.length==0) return 0;
int[] dp = new int[ratings.length];
dp[0] = 1;
// dp[i]存储的是第i个孩子得到的糖果
for(int i=1; i<ratings.length; i++) {
if(ratings[i] > ratings[i-1]) {
dp[i] = dp[i-1]+1;
continue;
}
if(ratings[i] == ratings[i-1]) {
dp[i] = 1;
continue;
}
dp[i] = 1;
if (dp[i] < dp[i-1]) {
continue;
}
for(int j=i-1; j>=0; j--) {
if (ratings[j]==ratings[j+1]) break;
if (ratings[j]>ratings[j+1]&&dp[j]>dp[j+1]) break;
if (ratings[j]<ratings[j+1]&&dp[j]<dp[j+1]) break;
dp[j]+=1;
}
}
int result = 0;
for(int a:dp) result+=a;
return result;
}
}
发表于 2020-04-17 10:14:43
回复(0)
public class Solution {
public int candy(int[] ratings) {
if (ratings == null || ratings.length == 0)
return 0;
int len = ratings.length, dp[] = new int[len], count = len;
for (int i = 1; i < len; ++i) {
if (ratings[i] > ratings[i - 1]) {
dp[i] = dp[i - 1] + 1;
} else if (ratings[i] < ratings[i - 1]) {
int j = i;
while (j > 0 && ratings[j] < ratings[j - 1] && dp[j] >= dp[j - 1])
dp[j - 1] = dp[j--] + 1;
}
}
for (int i = 0; i < len; ++i)
count += dp[i];
return count;
}
}
发表于 2019-01-23 19:16:11
回复(0)
class Solution {
public:
int candy(vector<int> &ratings) {
int n = ratings.size();
vector<int> res(n,1);
for(int i = 0; i < n; i++){
if(ratings[i+1] > ratings[i]){
res[i+1] = res[i] + 1;
}
}
for(int i = n-1; i >=1; i--){
if(ratings[i-1] > ratings[i] && res[i-1] <= res[i]){
res[i-1] = res[i] + 1;
}
}
int sum = 0;
for(int i = 0; i < n; i++){
sum += res[i];
}
return sum;
}
};
发表于 2018-07-27 20:54:33
回复(0)
这道题目采用动态规划的思想来求解，我觉得思想很重要
分为以下几个步骤：
1）当前孩子的rating比前面的孩子的rating高时：只需要考虑当前孩子的candies数目比前面孩子的candies的数目多至少一个即可；当前面的rating等于后面孩子的rating时，则题目没有说明，则可以比他多或者少；
2）当前孩子的rating比后面孩子的raitng低时：考虑当前孩子的后面的单调递减的孩子的数目，因为最后一个单调递减的孩子的手里至少还剩下一个糖果存在，则新建一个数组来存储单调递减孩子的数目，并将当前孩子的手里的糖果的数目设定为单调递减孩子的数目+1；
3）判断左边动态规划和右边动态规划的糖果数目，取其中糖果数目最大的即可；
代码如下：
class Solution {
public:
int candy(vector<int> &ratings) {
if(ratings.size()==0)
return -1;
int length=ratings.size();
vector<int> array(length);
for(int i=0;i<length;i++){
int space=0;
for(int j=i+1;j<length;j++){
if(ratings[j]>=ratings[j-1])
break;
else{
space++;
}
}
array[i]=space;
}
int result=0;
vector<int>candies(length);
candies[0]=array[0]+1;
result+=candies[0];
for(int i=1;i<length;i++){
int leftcandies=0;
if(ratings[i]>ratings[i-1])
leftcandies=candies[i-1]+1;
int rightcandies=array[i]+1;
candies[i]=max(leftcandies,rightcandies);
result+=candies[i];
}
return result;
}
};
public:
int candy(vector<int> &ratings) {
if(ratings.size()==0)
return -1;
int length=ratings.size();
vector<int> array(length);
for(int i=0;i<length;i++){
int space=0;
for(int j=i+1;j<length;j++){
if(ratings[j]>=ratings[j-1])
break;
else{
space++;
}
}
array[i]=space;
}
int result=0;
vector<int>candies(length);
candies[0]=array[0]+1;
result+=candies[0];
for(int i=1;i<length;i++){
int leftcandies=0;
if(ratings[i]>ratings[i-1])
leftcandies=candies[i-1]+1;
int rightcandies=array[i]+1;
candies[i]=max(leftcandies,rightcandies);
result+=candies[i];
}
return result;
}
};
发表于 2018-07-21 22:00:00
回复(1)
class Solution {
public:
int candy(vector<int> &ratings) {
int l = ratings.size(); if(l == 1) return 1; int s = 0; vector<int> a(l,1); for(int i=1;i<l;i++) if(ratings[i] > ratings[i-1]) a[i] = a[i-1] + 1; for(int i=l-2;i>=0;i--) if(ratings[i] > ratings[i+1] && a[i] <= a[i+1]) a[i] = a[i+1] + 1; for(int i=0;i<l;i++) s += a[i]; return s;
}
};
发表于 2017-09-25 01:16:23
回复(0)
class Solution {
public:
int candy(vector<int> &rat) {
vector<int> num(rat.size()+1,1);
for(int i=1;i<rat.size();i++){
if(rat[i]>rat[i-1]) num[i]=num[i-1]+1;
else{
int j=i-1;
while(j>=0 && rat[j]>rat[j+1] && num[j]<=num[j+1]){ num[j]+=1; j--; }
}
}
int res=0;
for(int i=0;i<rat.size();i++) res+=num[i];
return res;
}
};
发表于 2017-09-07 20:55:21
回复(0)
class Solution {
public:
int candy(vector<int> &ratings) {
int n = ratings.size();
int dp[n];
dp[0] = 1;
for (int i = 1; i < n; i++) {
if (ratings[i] > ratings[i - 1]) {
dp[i] = dp[i - 1] + 1;
} else {
dp[i] = 1;
}
}
for (int i = n - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) {
dp[i] = max(dp[i], dp[i + 1] + 1);
}
}
int sum = 0;
for (int i = 0; i < n; i++) {
sum += dp[i];
}
return sum;
}
};
发表于 2017-08-30 17:53:49
回复(0)
class Solution {
public:
int candy(vector<int> &ratings) {
vector<pair<int, int>> v;
for (int i = 0; i < ratings.size(); ++i)
v.push_back({ ratings[i], i });
sort(v.begin(), v.end(), [](const pair<int, int> &a, const pair<int, int> &b) {return a.first < b.first;});
vector<int> candies(ratings.size(), 0);
int n_count = 0;
for (auto e : v) {
int i = e.second;
int left = 0;
if (i - 1 >= 0) left = candies[i - 1];
int right = 0;
if (i + 1 < candies.size()) right = candies[i + 1];
candies[i] = 1;
if (left != 0 && ratings[i - 1] < ratings[i])
candies[i] = left + 1;
if (right != 0 && ratings[i + 1] < ratings[i])
candies[i] = max(candies[i], right + 1);
n_count += candies[i];
}
return n_count;
}
};
发表于 2017-08-06 15:50:59
回复(0)
import java.util.*;
public class Solution {
public int candy(int[] ratings) {
int[] arr1 = new int[ratings.length];
int[] arr2 = new int[ratings.length];
Arrays.fill(arr1, 1);
Arrays.fill(arr2, 1);
for (int i = 1; i < ratings.length; i ++) {
if(ratings[i] > ratings[i - 1]) arr1[i] = arr1[i - 1] + 1;
}
for (int i = ratings.length - 1; i >= 1; i --) {
if(ratings[i] < ratings[i - 1]) arr2[i - 1] = arr2[i] + 1;
}
int sum = 0;
for (int i = 0; i < ratings.length; i ++) {
sum += arr1[i] > arr2[i] ? arr1[i] : arr2[i];
}
return sum;
}
}
编辑于 2017-03-19 17:04:09
回复(0)
class Solution {
public:
int candy(vector<int>& ratings) {
int ret = 0;
int len = ratings.size();
vector<int> temp(len, 1);
for(int i = 1; i < len; i++){
if(ratings[i] > ratings[i-1]){
temp[i] = temp[i-1]+1;
}
}
for(int i = len-2; i >= 0; i--){
if(ratings[i] > ratings[i+1]){
temp[i] = max(temp[i], temp[i+1]+1);
}
}
for(int i = 0; i < len; i++){
ret += temp[i];
}
return ret;
}
};
发表于 2016-09-06 16:52:31
回复(0)
class Solution {
public:
int candy(vector<int> &ratings) {
int n=ratings.size();
if(n==0) return 0;
vector<int> res(n);//存每个小孩应发的糖果数
res[0]=1;
for(int i=1;i<n;i++){//不断遍历ratings并更新res
//如果新加入的小孩大于前一个小孩，则糖果比前一个小孩+1
if(ratings[i]>ratings[i-1]) {
res[i]=res[i-1]+1;
}
//关键：如果等于前一个小孩，则新小孩只需要分一个糖果，res不需要更新
else if(ratings[i]==ratings[i-1]) {
res[i]=1;
}
//如果小于前一个小孩,则新加入小孩分一个糖果，之前的小孩应该比他多分到糖果
else{
res[i]=1;
//如果前面的小孩只有一个糖果，需要更新res
if(res[i-1]==1) {
//前面的小孩都多分一个糖果，直到递增结束
int j=i-1;
for(;j!=0&&res[j]<res[j-1];j--){
res[j]++;
}
//关键：注意相等rating的情况
if(res[j]<=res[j+1] && ratings[j]!=ratings[j+1])res[j]++;
}
}
}
int sum=0;
for(auto e:res){
sum+=e;
}
return sum;
}
};
发表于 2016-07-04 01:27:26
回复(0)
问题信息
通过挑战的用户
查看代码-
2023-03-12 11:46:39 -
2023-03-08 14:20:56 -
2023-03-06 14:55:18
-
2023-02-26 21:06:38
-
2022-12-31 17:58:04
相关试题
-
评论(113) 来自【2021】小米秋招软件...
-
评论(387) 来自经典编程练习-难题卷
-
评论(1)
-
评论(1)
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
