本文主要是介绍leetcode刷题记录29-135. 分发糖果,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
问题描述
n
个孩子站成一排。给你一个整数数组ratings
表示每个孩子的评分。你需要按照以下要求,给这些孩子分发糖果:
- 每个孩子至少分配到
1
个糖果。- 相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果,计算并返回需要准备的 最少糖果数目 。
示例
示例 1:
输入:ratings = [1,0,2] 输出:5 解释:你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。示例 2:
输入:ratings = [1,2,2] 输出:4 解释:你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。第三个孩子只得到 1 颗糖果,这满足题面中的两个条件。提示:
n == ratings.length
1 <= n <= 2 * 10^4
0 <= ratings[i] <= 2 * 10^4
问题分析:
几个月前自己独立做出来的题,现在再做突然又没思路了。。。(印证了那句菜就多刷)事实上,读题发现其实问题就是要求我们根据给的rating数组,来规划一个分糖方案,在满足分数较高的要拿到更多的糖的基础上,计算出最少糖数。
很显然我们可以通过两次遍历来找到我们的分糖方案,首先第一次从左往右,如果当前孩子的rating大于前一个孩子的rating,那么这个孩子分到的糖数设置为前一个孩子的糖数+1。例如[1, 3, 2, 2, 1]这个数组,经过第一次得到的糖数组就是[1, 2, 1, 1, 1],可以看到这和我们需要得到的最终数组还有些不同。
因此我们要进行第二次遍历,从右往左,如果当前的孩子小于前一个孩子并且前一个孩子糖数<=当前孩子糖数(这个比较很关键,如果第一轮已经满足要求就不需要再更新糖数组),前一个孩子糖数=当前孩子糖数+1。第二次遍历之后就会得到[1, 2, 1, 2, 1]的结果数组,对数组求和即答案。
代码如下:
class Solution {
public:int candy(vector<int>& ratings) {// 最少每个孩子一颗糖vector<int> vec(ratings.size() , 1);// 正向遍历for(int i = 1; i < ratings.size(); i ++){if(ratings[i] > ratings[i - 1])vec[i] = vec[i - 1] + 1;}// 反向遍历for(int i = ratings.size() - 1; i >= 1; i --){if(ratings[i - 1] > ratings[i] && vec[i - 1] <= vec[i])vec[i - 1] = vec[i] + 1;}// 返回糖数组求和return accumulate(vec.begin(), vec.end(), 0);}
};
这篇关于leetcode刷题记录29-135. 分发糖果的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!