有N个小朋友站在一排，每个小朋友都有一个评分
你现在要按以下的规则给孩子们分糖果：
- 每个小朋友至少要分得一颗糖果
- 分数高的小朋友要他比旁边得分低的小朋友分得的糖果多
你最少要分发多少颗糖果？
[编程题]分糖果
import java.util.*;
public class Solution {
/**
*
* @param ratings int整型一维数组
* @return int整型
*/
public int candy (int[] ratings) {
// write code here
int len = ratings.length;
int sum=len;
int[] dp = new int[len];
for(int i=1;i<len;i++){
if(ratings[i]>ratings[i-1]){
dp[i] = dp[i-1]+1;
}
}
for(int i =len-1;i>0;i--){
if(ratings[i-1]>ratings[i]&&dp[i-1]<=dp[i]){
dp[i-1]=dp[i]+1;
}
}
for(int i:dp){
sum+=i;
}
return sum;
}
}
public class Solution {
/**
*
* @param ratings int整型一维数组
* @return int整型
*/
public int candy (int[] ratings) {
// write code here
int len = ratings.length;
int sum=len;
int[] dp = new int[len];
for(int i=1;i<len;i++){
if(ratings[i]>ratings[i-1]){
dp[i] = dp[i-1]+1;
}
}
for(int i =len-1;i>0;i--){
if(ratings[i-1]>ratings[i]&&dp[i-1]<=dp[i]){
dp[i-1]=dp[i]+1;
}
}
for(int i:dp){
sum+=i;
}
return sum;
}
}
发表于 2020-08-15 19:40:40
回复(0)
public class Solution {
/*动态规划思想：每个糖果的值都要受限与邻居结点，如果评估值比邻居结点大，那么得到的糖果也比邻居结点多，因此都需要与左右邻居结点进行比较。*/
public int candy(int[] ratings) {
if(ratings == null || ratings.length == 0)
return 0;
int len = ratings.length;
int[] dp = new int[len];
int sum = 0;
//初始化，给每个小朋友先分发一个糖果
for(int i = 0; i < len; i++){
dp[i] = 1;
}
//从左往右遍历，右边的小朋友分数比左边的小朋友分数高，则右边分数高的小朋友糖果+1
for(int i = 0; i < len -1; i++){
//和左邻居的比较
if(ratings[i+1] > ratings[i])
dp[i+1] = dp[i] + 1;
}
//从右往左遍历，左边的小朋友分数比右边的小朋友分数高，则左边分数高的小朋友糖果+1
for(int j = len - 2; j >= 0; j--){
//和右邻居的比较
if(ratings[j] > ratings[j+1] && dp[j] <= dp[j+1])
dp[j] = dp[j+1] + 1;
}
//计算总糖果数
for(int i = 0; i < len; i++){
sum += dp[i];
}
return sum;
}
}
编辑于 2020-02-26 21:05:42
回复(0)
// 思路：遍历数组，给当前元素分配1，
// 若前一个元素大于当前元素且其分配值小于等于当前的元素，则重新为其分配值为当前值+1,再次往前查看，直到不满足该条件
// 若当前值大于前一个值，则其分配值为前一个的值+1
public class Solution {
public int candy(int[] ratings) {
int sum = 0;
int cur = 1;
int res[] = new int[ratings.length];
for(int i = 0; i < ratings.length; i++) {
res[i] = 1;
int j = i;
//不是第一个元素，且前一个元素大于当前元素，但其分配值不大于当前元素的分配值
while(j>=1 && ratings[j-1]>ratings[j] && res[j-1]<=res[j]) {
res[j-1] = res[j] + 1;
j--;
}
// 不是第一个元素且其值比前一个元素大，则为前一个元素的分配值加1
if(i>0 && ratings[i]>ratings[i-1]) res[i] = res[i-1] + 1;
}
for(int i = 0; i < res.length; i++) {
sum += res[i];
}
return sum;
}
}
发表于 2019-04-11 15:23:37
回复(0)
用dp[i]记录前i个孩子的最小分配值。
用num[]记录目前糖果的分配情况。
从左到右遍历,有三种情况：
- 如果rating比前面一个小
- 如果rating和前面一个相等
- 如果rating比前面一个大
public static int candy(int[] ratings) {
int[] num = new int[ratings.length];
int[] dp = new int[ratings.length];
dp[0] = 1;
num[0] = 1;
for(int i=1;i<ratings.length;i++){
// 如果rating比前面一个小
if(ratings[i]<ratings[i-1]){
//如果前面一个孩子的糖果数为1，前面的要重新分配。
if(num[i-1]==1){
num[i-1]+=1;
for(int j=i-2;j>=0;j--){
if(ratings[j]>ratings[j+1]&&num[j]==num[j+1]){
num[j]=num[j]+1;
}else{
break;
}
}
for(int j=0;j<i;j++){
dp[i]+=num[j];
}
dp[i]+=1;
}else{
dp[i]=dp[i-1]+1;
}
num[i]=1;
}
// 如果rating与前面一个相等，那么这个孩子就分给他一个
if(ratings[i]==ratings[i-1]){
dp[i]=dp[i-1]+1;
num[i]=1;
}
// 如果rating比前面一个大，比前面一个多分一个
if(ratings[i]>ratings[i-1]){
dp[i]=dp[i-1]+num[i-1]+1;
num[i]=num[i-1]+1;
}
}
return dp[ratings.length-1];
}
发表于 2018-09-30 13:14:16
回复(0)
import java.util.Arrays;
public class Solution { public int candy(int[] ratings) { int len=ratings.length; if(ratings.length==0) return 0; int[] count=new int[len+1]; Arrays.fill(count, 1); //从左向右扫描 for(int i=1;i<len;i++){ if(ratings[i]>ratings[i-1]){ count[i]=count[i-1]+1; } } //从右向左扫描 for(int i=len-2;i>=0;i--){ if(ratings[i]>ratings[i+1]&&count[i]<=count[i+1]){ count[i]=count[i+1]+1; } } int sum=0; for(int i=0;i<len;i++){ sum+=count[i]; } return sum; }
}
发表于 2018-08-24 11:10:34
回复(0)
dp思路
- start记录开始降序的位置
每次遇到降序从后往前更新到start为止
public class Solution { public int candy(int[] rating) { if(rating.length<=1) return rating.length; int[] dp=new int[rating.length]; int start=0; int sum=0; dp[0]=1; for(int i=1;i<rating.length;i++){ if(rating[i]>rating[i-1]){ dp[i]=dp[i-1]+1; start=i; }else if(rating[i]==rating[i-1]){ dp[i]=1; start=i; }else{ dp[i]=1; for(int j=i-1;j>=start;j--){ if(dp[j]<=dp[j+1]) dp[j]=dp[j+1]+1; } } } for(int i=0;i<rating.length;i++){ sum+=dp[i]; } return sum; } }
发表于 2018-04-10 22:06:41
回复(0)
int []array = new int[ratings.length];
Arrays.fill(array, 1);
for(int i=1;i<array.length;i++){
if(ratings[i]>ratings[i-1])
array[i] = array[i-1] + 1;
}
for(int i=array.length-2;i>=0;i--){
if(ratings[i]>ratings[i+1]&&array[i]<=array[i+1])
array[i] = array[i+1]+1;
}
return Arrays.stream(array).sum();
Arrays.fill(array, 1);
for(int i=1;i<array.length;i++){
if(ratings[i]>ratings[i-1])
array[i] = array[i-1] + 1;
}
for(int i=array.length-2;i>=0;i--){
if(ratings[i]>ratings[i+1]&&array[i]<=array[i+1])
array[i] = array[i+1]+1;
}
return Arrays.stream(array).sum();
发表于 2018-03-20 16:07:41
回复(0)
public int candy(int[] ratings) {
int result = 0;
int sum = ratings.length;
int candys[] = new int[sum];
//初始化，每个孩子一个糖果
for(int i=0;i<sum;i++){ candys[i] = 1; } //从左向右遍历，保证右边分数高的比左边的糖果多一个 for(int i=0;i<sum-1;i++){ if(ratings[i+1]> ratings[i]){
candys[i+1] = candys[i]+1;
}
}
//从右向左遍历，保证左边分数高的孩子，比右边的分数低的孩子至少多一块糖果
for(int i=sum-1;i>0;i--){
if(ratings[i-1] > ratings[i]){
candys[i-1] = Math.max(candys[i-1], candys[i]+1);
}
}
for(int i=0;i<sum;i++){
result+=candys[i];
}
return result;
}
编辑于 2018-02-01 08:48:03
回复(0)
/**
问题：
有N个孩子站成一排。每个孩子被分配一个评价值。
你给这些孩子的糖果有以下要求：
每个孩子必须至少有一块糖。
评级较高的孩子比邻居得到更多的糖果。
你最少要给多少糖？
思路：
遍历两边(小的只和大的比，小的不和更小的比)，首先每个人得一块糖，第一遍从左到右，若当前点比前一个点高就比前者多一块。
这样保证了在一个方向上满足了要求。第二遍从右往左，若左右两点，左侧高于右侧，但
左侧的糖果数不多于右侧，则左侧糖果数等于右侧糖果数+1，这就保证了另一个方向上满足要求
*/
import java.util.*;
public class Solution {
public int candy(int[] ratings)
{ int n = ratings.length;
if(ratings==null||n==0)
return -1;
int sum = 0;
int[] count = new int[n];//count是表示每个元素的糖果数量,ragting是表示每个元素的权重
//每个孩子至少有一个糖果
Arrays.fill(count,1);
//正方向排序一次
for(int i=1;i<n;i++)
{
if(ratings[i]>ratings[i-1])
{
count[i] = count[i-1]+1;//权重高的至少比相邻的多一个
}
}
//逆方向排序一次
for(int i=n-1;i>0;i--)
{
//ratings权重值不能相等，count值需要考虑相等情况
if((ratings[i]<ratings[i-1])&&(count[i]>=count[i-1]))
{
count[i-1] = count[i]+1;
}
sum +=count[i];
}
//sum还需要包含count【0】
sum +=count[0];
return sum;
}
}
发表于 2017-08-01 10:33:40
回复(0)
public class Solution {
public int candy(int[] ratings) {
if (ratings == null || ratings.length == 0)
return 0;
int len = ratings.length;
return candyNum(ratings, 0, 0);
}
public int candyNum(int[] ratings, int startIndex, int beforeCandyNum) {
int len = ratings.length;
if (startIndex >= len)
return 0;
if (startIndex == len - 1)
return beforeCandyNum + 1;
int curIndex = startIndex;
while (curIndex < len - 1) {
if (ratings[curIndex + 1] < ratings[curIndex]) {
++curIndex;
} else
break;
}
int nowCandyNum = 0;
if (curIndex == startIndex) {
nowCandyNum = beforeCandyNum + 1;
} else {
for (int i = curIndex; i >= startIndex; --i) {
if (i == startIndex && curIndex - startIndex + 1 < beforeCandyNum + 1) {
nowCandyNum += beforeCandyNum + 1;
} else {
nowCandyNum += curIndex - i + 1;
}
}
}
if (curIndex == len - 1)
return nowCandyNum;
else {
if (ratings[curIndex + 1] == ratings[curIndex]) {
return nowCandyNum + candyNum(ratings, curIndex + 1, 0);
} else {
if (curIndex == startIndex)
return nowCandyNum + candyNum(ratings, curIndex + 1, nowCandyNum);
else
return nowCandyNum + candyNum(ratings, curIndex + 1, 1);
}
}
}
}
发表于 2017-07-20 21:32:09
回复(0)
public class Solution {
public int candy(int[] ratings) {
if(ratings == null || ratings.length == 0)
return 0;
int sum = 0;
int[] help = new int[ratings.length];
for(int i = 0; i < help.length; i++){
help[i] = 1;
}
for(int i = 1; i < ratings.length; ++i){
if(ratings[i] > ratings[i-1]){
help[i] = help[i-1] + 1;
}
}
for(int i = ratings.length - 2; i >= 0; --i){
if(ratings[i] > ratings[i+1] && help[i] <= help[i+1]){
help[i] = help[i+1] + 1;
}
}
for(int i = 0; i < help.length; i++){
sum += help[i];
}
return sum;
}
}
发表于 2017-07-11 15:13:07
回复(0)
public class Solution {
public int candy(int[] ratings) {
int len = ratings.length;
if(len < 1) return 0;
if(len == 1) return 1;
boolean isOK = false;
int[] candys = new int[len];
//糖果每个人初始化为1
for(int i = 0; i < len; i++){ candys[i] = 1; }
int counts = 0;
while(!isOK){
//遍历数组 判断当前孩子的rating是否比旁边的高 是的话糖果是否比旁边的少 是的话改变糖果值
//当遍历一遍 糖果值都没有改变的时候 说明分配完成
isOK = true;
for(int i = 0; i < len; i++){
if(i == 0 ){
if(ratings[i] > ratings[i+1] && candys[i] <= candys[i+1]){
isOK = false;
candys[i] = candys[i+1] + 1;
//counts++;
}
}
else if(i == len - 1){
if(ratings[i] > ratings[i-1] && candys[i] <= candys[i-1]){
isOK = false;
candys[i] = candys[i-1] + 1;
//counts++;
}
}
else{
if(ratings[i] > ratings[i+1] && candys[i] <= candys[i+1]){
isOK = false;
candys[i] = candys[i+1] + 1;
//counts++;
}
if(ratings[i] > ratings[i-1] && candys[i] <= candys[i-1]){
isOK = false;
candys[i] = candys[i-1] + 1;
//counts++;
}
}
}
}
for(int i = 0; i < len; i++){
counts += candys[i];
}
return counts;
}
}
发表于 2017-03-31 15:45:06
回复(0)
public class Solution { public int candy(int[] ratings) { if (ratings == null || ratings.length == 0) return 0; int total = 1, prev = 1, countDown = 0; for (int i = 1; i < ratings.length; i++) { if (ratings[i] >= ratings[i-1]) { if (countDown > 0) {
total += countDown*(countDown+1)/2; // arithmetic progression if (countDown >= prev) total += countDown - prev + 1;
countDown = 0;
prev = 1;
}
prev = ratings[i] == ratings[i-1] ? 1 : prev+1;
total += prev;
} else countDown++;
} if (countDown > 0) { // if we were descending at the end total += countDown*(countDown+1)/2; if (countDown >= prev) total += countDown - prev + 1;
} return total;
}
}
发表于 2017-03-11 19:35:35
回复(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)
问题信息
通过挑战的用户
查看代码-
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
相关试题
-
评论(387) 来自经典编程练习-难题卷
-
评论(113) 来自【2021】小米秋招软件...
-
评论(1)
-
评论(1)
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
