色轮 网站,企业网站的总体设计,免费域名空间注册,上海商城一#xff1a;题目
老师想给孩子们分发糖果#xff0c;有 N 个孩子站成了一条直线#xff0c;老师会根据每个孩子的表现#xff0c;预先给他们评分。
你需要按照以下要求#xff0c;帮助老师给这些孩子分发糖果#xff1a;
每个孩子至少分配到 1 个糖果。 评分更高的孩…一题目
老师想给孩子们分发糖果有 N 个孩子站成了一条直线老师会根据每个孩子的表现预先给他们评分。
你需要按照以下要求帮助老师给这些孩子分发糖果
每个孩子至少分配到 1 个糖果。 评分更高的孩子必须比他两侧的邻位孩子获得更多的糖果。 那么这样下来老师至少需要准备多少颗糖果呢
示例 1
输入[1,0,2] 输出5 解释你可以分别给这三个孩子分发 2、1、2 颗糖果。 示例 2
输入[1,2,2] 输出4 解释你可以分别给这三个孩子分发 1、2、1 颗糖果。 第三个孩子只得到 1 颗糖果这已满足上述两个条件。
二思路
这里的思路是局部最优,分为两次遍历 都是找最优的结果 第一次遍历从左往右 右边的评分比左边的高则其糖果个数在左边糖果个数的基础上加一 第二次遍历从右往左 如果左边的评分比右边的高 且其个数不大于右边的个数 则其糖果数在右边糖果数的基础上加一 解释第二次遍历因为我们要求比相邻的评分低糖果数多就行一种情况是他比两边都高 那么在第一次遍历 加一 过后到第二次就不用再加一了故第二次遍历 当中的 且其个数。。。。说的就是这个原因
三上码
class Solution {
public:int candy(vectorint ratings) {//这里的思路是局部最优,分为两次遍历 都是找最优的结果//第一次遍历从左往右 右边的评分比左边的高则其糖果个数在左边糖果个数的基础上加// //一//第二次遍历从右往左 如果左边的评分比右边的高 且其个数不大于右边的个数 则其糖 果数在右边糖果数的基础上加一//解释第二次遍历因为我们要求比相邻的评分低糖果数多就行一种情况是他比两边都高// 那么在第一次遍历 加一 过后到第二次就不用再加一了故第二次遍历// 当中的 且其个数。。。。说的就是这个原因mapint,intm;mapint,int:: iterator mt;for(int i 0; i ratings.size(); i){m[i] 1;}//从左往右边for(int i 0; i ratings.size() - 1; i){if(ratings[i] ratings[i1]){m[i1] m[i] 1;}} //从右往左for(int i ratings.size() - 1;i 0; i--){if(ratings[i-1] ratings[i] m[i-1] m[i]){m[i-1] m[i] 1;}} int sum 0;for(mt m.begin(); mt ! m.end(); mt){summt-second;} return sum; }
};加油 BOY 如有问题请留言
