成都建设银行保安招聘网站,seo全称是什么意思,中国建设银行网上银行官网,WordPress无法加载插件js文章目录 题目解① 穷举法#xff0c;用时3ms#xff0c;超过26.93%②穷举法改进#xff0c;用时2ms#xff0c;超过97.78% 题目
n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
你需要按照以下要求#xff0c;给这些孩子分发糖果#xff1a;
每个… 文章目录 题目解① 穷举法用时3ms超过26.93%②穷举法改进用时2ms超过97.78% 题目
n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
你需要按照以下要求给这些孩子分发糖果
每个孩子至少分配到 1 个糖果。相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果计算并返回需要准备的 最少糖果数目 。
示例 1
输入ratings [1,0,2]
输出5
解释你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。示例 2
输入ratings [1,2,2]
输出4
解释你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。第三个孩子只得到 1 颗糖果这满足题面中的两个条件。解
① 穷举法用时3ms超过26.93%
数组正序当前元素和前后的元素比较如果大则要保证比相邻的同学糖果多1个数组逆序检查如果当前同学的评分比相邻同学高则保证比相邻同学糖果多1个。
注下面的代码为了简化设置了每个同学初始获得的糖果为0计算完成之后再给每个同学发一个糖果保证每人至少1个所以candy数组并不是实际发放的糖果数目还要在计算之后每个元素1
问题为什么正序之后还要逆序检查
答假设没有逆序检查用例ratings输入为[1,2,87,87,87,2,1]时candy[0,1,2,0,1,1,0]。当for循环运行到最后一个‘87’时candy[0,1,2,0,0,0,0]下一个评分为‘2’的同学此时分配的糖果数目为0所以最后一个‘87’分的同学满足比相邻同学的糖果多1个分配糖果数目为1即candy[0,1,2,0,1,0,0]。然后运行至分数为‘2’的同学那里按照和相邻同学对比的原则最终可得1个糖果因为他的糖果数目发生改变所以之前分配给‘87’分同学的数目就少了一个不满足原题目条件故最后需要逆序检查。
问题既然要检查为什么不改成如果当前元素的糖果发生变化就对上一个进行检查呢
答这个思路尝试后发现如果当前同学的糖果增加了上一个同学的糖果可能也会变化上一个同学的糖果如果变化那么上上个同学也应该检查。如此循环反复就会变成每一次发生变化之后就得检查前面所有的同学是否要改变比逆序检查一次所耗费的时间更多。举个例子ratings[1,16,10,8,7,3,2]如果按照只检查上一次的话最终的candy[0,1,2,2,2,1,0]不符合题目要求。
class Solution {public int candy(int[] ratings) {int[] candynew int[ratings.length];//数组初始所有元素为0int num0;//数组正序检查每个同学和相邻同学评分for(int i0;iratings.length;i){if(i!ratings.length-1 ratings[i]ratings[i1]){// 如果该同学比下一个同学分数高则他的糖果要比下一个同学多1个candy[i]candy[i1]1;}if(i!0 ratings[i]ratings[i-1]){// 如果该同学比上一个同学分数高则他的糖果要比下一个同学多1个candy[i]candy[i-1]1;}}//数组逆序检查分配是否有误for(int iratings.length-1;i0;i--){if(i!0 ratings[i]ratings[i-1] candy[i]candy[i-1]){// 如果该同学比上一个同学分数高并且糖果少于上一个同学则他要比上个同学多一个candy[i]candy[i-1]1;}if(i!ratings.length-1 ratings[i]ratings[i1] candy[i]candy[i1]){// 如果该同学比下一个同学分数高并且糖果少于下一个同学则他要比下个同学多一个candy[i]candy[i1]1;}}for(int j0;jratings.length;j){// 将数组的所有元素相加numcandy[j];}return numratings.length;//每个同学至少一个糖果所以返回值加上length}
}②穷举法改进用时2ms超过97.78%
和①的区别在于①每次循环都是和前后两个元素进行比较②正循环的时候只和左边元素比较倒序的时候只和右边元素比较
删掉了两个if的部分对代码进行了简化
class Solution {public int candy(int[] ratings) {int[] candynew int[ratings.length];int num0;for(int i0;iratings.length;i){if(i!0 ratings[i]ratings[i-1]){candy[i]candy[i-1]1;}}for(int iratings.length-1;i0;i--){if(i!ratings.length-1 ratings[i]ratings[i1] candy[i]candy[i1]){candy[i]candy[i1]1;}}for(int j0;jratings.length;j){numcandy[j];}return numratings.length;}
}
