【LeeCode笔试题目】

有n个孩子根据分数来分糖果，要求：

1、每个孩子都至少能分到一个糖果；

2、相邻的孩子，分数高的那一个应该分到比分数低的孩子更多的糖果；

3、若相邻的孩子的分数相同，则不要求多分糖果；

要求计算n个孩子最少要分掉多少糖果？

示例?1:

输入: [1,0,2]
输出: 5
解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。

原题指路：力扣https://leetcode.cn/problems/candy/

【错误代码】

//arrLen孩子个数
//arr表示arrLen个孩子分数所对应的数组
#include <iostream>
#include "stdio.h"

int solution(int *arr, int arrLen)
{
	int i;
	int candyave[arrLen]; //每个孩子分到的糖果数组
	int candynum=0;  //总共分配的糖果数
	
	//每个孩子分到的糖果基数
	for(i = 0; i < arrLen; i++){
		candyave[i]=1;
	}
	
	//根据分数进行加糖果
	for(i = 0; i < arrLen-1; i++)
	{
		if(arr[i] < arr[i+1]){
			candyave[i+1]=candyave[i]+1;
		}else if(arr[i] > arr[i+1]){
			candyave[i]=candyave[i+1]+1;
		}
	}
	
	//计算总共要多少糖果
	for(i = 0; i < arrLen; i++){
		candynum=candynum+candyave[i];
	}
	
	return candynum;
}

int main()
{
    int arrLen=5;
	int arr[5] = {18,10,8,9,4};
	int num;
	
	num=solution(arr, arrLen);
	printf("least candy number:%d\n",num);
	
	return 0;
}

计算结果是：

least candy number:8

这是昨晚银行在线笔试时候写的代码，根据回忆写了下来，由于当时不能在线调试，只显示不能通过所有测试用例。调试和逻辑对比后发现，上述代码只做到了相邻两个元素之间单次比较，的确错误。

【正确思路】

?借鉴，力扣思路，在错误答案的基础上补全逻辑，如下

int candy(int* ratings, int ratingsSize){

	int i,j;
	int decrease_num=0;
	int candyave[ratingsSize]; //每个孩子分到的糖果数组
	int candynum=0;  //总共分配的糖果数
    int arrLen=ratingsSize;
    int *arr=ratings;
	
	//每个孩子分到的糖果基数
	for(i = 0; i < arrLen; i++){
		candyave[i]=1;
	}
	
	//根据分数进行加糖果
	for(i = 0; i < arrLen-1; i++)
	{
		if(arr[i] < arr[i+1]){
			candyave[i+1]=candyave[i]+1;
			decrease_num=0;
		}else if(arr[i] > arr[i+1]){
			candyave[i]=candyave[i+1]+1;
			decrease_num=decrease_num+1;
			//所有递减序列需要+1
			if(decrease_num != 1 || decrease_num != 0){
				for(j=1;j<decrease_num;j++){
					candyave[j]=candyave[j]+1;
				}
			}
		}else if(arr[i] == arr[i+1] && decrease_num != 0){
			decrease_num=decrease_num+1;
		}else{
			decrease_num=0;
		}
	}
	
	//计算总共要多少糖果
	for(i = 0; i < arrLen; i++){
		candynum=candynum+candyave[i];
	}
	
	return candynum;
}

执行成功：