本站消息

站长简介


前每日优鲜python全栈开发工程师,自媒体达人,逗比程序猿,钱少话少特宅,我的公众号:想吃麻辣香锅

  python大神匠心打造,零基础python开发工程师视频教程全套,基础+进阶+项目实战,包含课件和源码

  出租广告位,需要合作请联系站长



+关注
已关注

分类  

暂无分类

标签  

暂无标签

日期归档  

2020-06(17)

2020-07(32)

2020-08(44)

2020-09(61)

2020-10(63)

贪心策略、分发糖果

发布于2021-01-29 11:39     阅读(400)     评论(0)     点赞(11)     收藏(3)


0

1

2

3

4



135. 分发糖果

https://leetcode-cn.com/problems/candy/

老师想给孩子们分发糖果,有 N 个孩子站成了一条直线,老师会根据每个孩子的表现,预先给他们评分。

你需要按照以下要求,帮助老师给这些孩子分发糖果:

  • 每个孩子至少分配到 1 个糖果。
  • 评分更高的孩子必须比他两侧的邻位孩子获得更多的糖果。

那么这样下来,老师至少需要准备多少颗糖果呢?

 

示例 1:

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

示例 2:

输入:[1,2,2]
输出:4
解释:你可以分别给这三个孩子分发 1、2、1 颗糖果。
     第三个孩子只得到 1 颗糖果,这已满足上述两个条件。

可以采用贪心策略,并不一定需要排序,两侧同时分配比较困难,先从左往右扫描一遍使得所有左侧满足条件,再从右往左扫描一遍使得右侧满足条件。

提交成功的c++代码如下:

 

  1. class Solution {
  2. public:
  3. int candy(vector<int>& ratings) {
  4. int ans = 0;
  5. // 记录最终糖果总数
  6. int len = ratings.size();
  7. if(len==1){
  8. return 1;
  9. // 边界条件,只有1个孩子1颗糖就ok
  10. }
  11. // 有多少个孩子,每个孩子就初始化1个糖果
  12. vector<int> num(len,1);
  13. // 从左往右扫一遍,保证右边评分更高的孩子获得更多糖果(比左侧评分低的多1颗就行)
  14. for (int i=0;i<len-1;++i){
  15. if(ratings[i]<ratings[i+1]){
  16. num[i+1] = num[i]+1;
  17. }
  18. }
  19. // 从右边往左边扫一遍,保证所有左边评分更高的孩子获得更多糖果,若左侧已经满足条件则跳过
  20. for(int i=len-1;i>=1;i--){
  21. if(ratings[i-1]>ratings[i]&& num[i-1]<=num[i]){
  22. num[i-1] = num[i] + 1;
  23. }
  24. }
  25. // 统计总共最少的糖果数目
  26. for (int i=0;i<len;++i){
  27. ans+=num[i];
  28. }
  29. return ans;
  30. }
  31. };

 

 

 

提交通过的python代码段如下:

  1. class Solution(object):
  2. def candy(self, ratings):
  3. """
  4. :type ratings: List[int]
  5. :rtype: int
  6. """
  7. kids = len(ratings)
  8. nums = [1 for i in range(kids)]
  9. # 从左往右,使得所有左侧满足条件
  10. for i in range(kids-1):
  11. if ratings[i]<ratings[i+1]:
  12. nums[i+1] = nums[i] +1
  13. i = kids-1
  14. # 从右边往左,使得素有右侧满足条件
  15. while (i>=1):
  16. if ratings[i-1]>ratings[i] and nums[i-1]<=nums[i]:
  17. nums[i-1] = nums[i]+1
  18. i-=1
  19. ans =0
  20. for j in range(kids):
  21. ans+=nums[j]
  22. return ans

 

原文链接:https://blog.csdn.net/qq_37437892/article/details/113320206




0

1

2

3

4



所属网站分类: 技术文章 > 博客

作者:精灵

链接:https://www.pythonheidong.com/blog/article/803770/4146eca92681f33e9f2f/

来源:python黑洞网

任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任

11 0
收藏该文
已收藏

评论内容:(最多支持255个字符)